Classical and Motion Planning

Introduction

In this project, you will write a PDDL domain for a short-order robot cook (Question 1), and then implement RRT and RRT* (Questions 2-7) and let them drive two robots: an Among Us crewmate hunting the other crewmates around the Skeld, and the robot cook's arm.

Download: all the code and supporting files are in planning.zip. Download it, unzip it, and change into the planning directory. The code needs numpy, and the Among Us game also needs Pillow (Question 1 needs one more library; see Planner Setup):

python3.12 -m pip install numpy pillow

Play the games: drive the robot cook with the arrow keys (the trackpad moves the dot in configuration space), and press SPACE at a goal to act. Orders come in on the wire; the header tells you what to do next:

python3.12 robotCook.py

The crewmate moves with the arrow keys. Once you have implemented RRT, both games plan for themselves: press 'p' in the robot cook, and the crewmate starts hunting the moment the game opens.

python3.12 amongUs.py

As in previous programming assignments, this assignment includes an autograder for you to grade your answers on your machine. This can be run with the command:

python3.12 autograder.py

See the autograder tutorial in Project 0 for more information about using the autograder.

The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore.

Files you will edit

Files you might want to look at

Files you will not edit

Files to Edit and Submit: You will fill in portions of rrt.py and write robot-cook_domain.pddl, robot-cook_cook1.pddl, and robot-cook_cook2.pddl during the assignment. You should submit these files with your code and comments. Please do not change the other files in this distribution or submit any of our original files other than these files.

Evaluation: Your code will be autograded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. However, the correctness of your implementation, not the autograder's judgements, will be the final judge of your score. If necessary, we will review and grade assignments individually to ensure that you receive due credit for your work.

Academic Dishonesty: We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else's code and submit it with minor changes, we will know. These cheat detectors are quite hard to fool, so please don't try. We trust you all to submit your own work only; please don't let us down. If you do, we will pursue the strongest consequences available to us.

Getting Help: You are not alone! If you find yourself stuck on something, contact the course staff for help. Office hours, section, and the discussion forum are there for your support; please use them. If you can't make our office hours, let us know and we will schedule more. We want these projects to be rewarding and instructional, not frustrating and demoralizing. But, we don't know when or how to help unless you ask.

Discussion: Please be careful not to post spoilers.

Assignment FAQ

We have compiled a list of frequently asked questions and common mistakes on various problems in this assignment. Please read this list carefully, and refer back to this before asking any questions on the discussion board.

• Question 1: PDDL is case-insensitive, and a semicolon starts a comment. A missing close parenthesis is usually reported on the next action.
• Question 1: The autograder compares the names of the actions in the optimal plan, in order, with ours. The six action names and the three file names have to match exactly; the predicates, parameters, and object names are up to you.
• Question 2: When the segment is blocked, return None, not an empty list. Legality is only checked at the interpolated configurations, the ones the agent will actually visit.
• Question 4: Call config_space.sample() exactly once per call to growRRT. The tests hand you specific samples, and the random worlds are seeded, so an extra call changes the tree.
• Question 4: Use config_space.getVector(q_nearest, q_rand) for the direction from q_nearest to q_rand, not q_rand - q_nearest. They agree in these worlds, but not in every configuration space.
• Questions 5-7: The neighbors within the rewire radius may not include the nearest node. growRRTStar has to add it, or a small radius could never grow the tree.
• Question 6: Reparent with neighbor.updateParent; it keeps the children lists and the cached costs consistent for the whole subtree.

The Robot Cook

The robot cook is a two-link arm bolted to the front of a griddle station, seen from above. Orders arrive on the wire at the back. For each pancake, the arm has to swap to the ladle at the tool rack, fill the ladle from the batter tank, pour the pancake anywhere it fits on the griddle, swap back to the flipper, flip the pancake, lift it, and carry it to a plate. When the plate holds the whole order, the ticket is pulled and the next order starts.

That is two planning problems at two levels. Which actions, in what order, is classical planning, and Question 1 writes it down in PDDL. How the arm gets from one goal to the next without hitting the dish stacks, the tank, or the splash guard is motion planning in the space of joint angles, and that is RRT, Questions 2-7. The game's own planner (press 'p') is your rrt.py.

Planner Setup

Question 1 uses the unified-planning library, which reads PDDL and hands the problem to a planner. We use Fast Downward in its optimal configuration. Install both with:

python3.12 -m pip install "unified-planning[fast-downward]"

(On the Andrew Linux servers, add --user.) Then test the installation on the blocks world files from the pre-reading:

python3.12 plan.py blocksworld_domain.pddl blocksworld_3blocks.pddl

This should print a six-step plan and its action names:

Found plan : SequentialPlan:
    unstack(c, a)
    putdown(c)
    pickup(b)
    stack(b, c)
    pickup(a)
    stack(a, b)
Action names: unstack putdown pickup stack pickup stack

Please let us know if you have issues with this setup.

Question 1 (8 points): The Robot Cook in PDDL

Write the robot cook as a planning domain and two problems, from scratch, in three new files: robot-cook_domain.pddl, robot-cook_cook1.pddl, and robot-cook_cook2.pddl. The blocks world files are your template, and the pre-reading walks through them line by line. Stick to :strips: preconditions are conjunctions of predicates, and effects add and delete predicates.

The arm holds one tool at a time, the ladle or the flipper, and the other hangs on the rack. A tool is either empty or holding something: the ladle holds batter after a fill, and the flipper holds a pancake after a lift. Each pancake starts as an order and goes through four stages: poured onto the griddle (raw), flipped, on the flipper, and served. A pancake is served onto the plate, or onto a pancake that is already on the plate, but only if nothing is on the destination yet.

Model that state however you like: the predicates, each action's parameters, and the names of the objects are your design. The six action names are fixed, because the autograder identifies actions by name, so use exactly these:

Both problems start with the arm holding the empty flipper and one clear plate. In cook1, one pancake is ordered, and the goal is that pancake on the plate. In cook2, two pancakes are ordered, and the goal is a short stack: the first pancake on the plate with the second on top of it. Nothing else is part of either goal. Remember that :init has to be complete and :goal should not be.

Plan with:

python3.12 plan.py robot-cook_domain.pddl robot-cook_cook1.pddl

The autograder runs the same optimal planner on your three files and compares the sequence of action names in the plan, arguments dropped, with ours. For cook1, that is switch fill pour switch flip lift serve. For cook2, the optimal plan has twelve steps: the two pancakes can be finished together (... flip flip lift serve lift serve) or one after the other (... flip lift serve flip lift serve), and both pass. If your plan comes out shorter than ours, check for a missing precondition or an effect that gives away too much. If it comes out longer, or there is no plan, check for a missing effect, an extra precondition, an incomplete :init, or a goal that asks for more than it should.

Two optimal plans do not pin down six actions, so the autograder also checks the rules one at a time. Using your problem files, it asks whether a short sequence of actions, by name, can be applied from the initial state with any choice of arguments: switch pour (pouring an empty ladle), switch fill pour flip (flipping with the ladle), and so on must be impossible, and a few sequences such as switch fill pour fill must be possible. Each test file in test_cases/q1 says which rule it checks, and plan.sequencePossible lets you try your own sequences.

To test and debug your code, run:

python3.12 autograder.py -q q1

Configuration Spaces and RRT

The rest of the project is rrt.py. It plans in any ConfigurationSpace (configuration_space.py): an object that can sample() a random configuration, say whether a configuration isLegal (and whether a whole list of them is allLegal), and give the getVector and distance between two configurations. A configuration is a NumPy array of K numbers. Nothing in rrt.py should care what K is: the crewmate's configuration is its \((x, y)\) position, the two-link arm's is \((\theta_1, \theta_2)\), and python3.12 robotCook.py --links 4 gives you a four-joint arm and a 4-dimensional configuration space.

The tree is made of RRTNodes. Each node holds a configuration, its parent, its children, and path_from_parent: the list of configurations from the parent to the node, one action apart. An action is the vector from one configuration to the next, and the agent can only move so far per action: step_limits caps each dimension of an action. That is different from max_edge, the longest edge RRT will add to the tree; an edge is usually several actions long. The provided interpolate chops a segment into the fewest steps that respect step_limits, and rrt() at the top of the file runs the main loop for you. Read the docstrings; they say what each function you write takes and returns.

The test cases build small worlds and trees with rrtUtil.py, and you can draw any of them. For example, the tree that Questions 3, 5 and 6 use:

>>> from rrtUtil import *
>>> world = BoxWorld([-10, -10], [10, 10])
>>> tree, nodes = buildTree([[0, 1], [1, 1], [2, 2], [2, 0], [5, 0], [5, 1]], [None, 0, 1, 1, 3, 4], (1, 1), world)
>>> print(tree)
>>> plotTree(tree, plotWorld(world)); show()

Question 2 (5 points): Segments and Costs

Implement getValidSegmentPath(q1, q2, step_limits, config_space) in rrt.py: interpolate from q1 to q2 and return the list of configurations if they are all legal, and None if any of them is not.

Then implement computePathCost(path): the sum of the Euclidean distances between consecutive configurations.

To test and debug your code, run:

python3.12 autograder.py -q q2

You can also run one test at a time with the -t flag, for example python3.12 autograder.py -t test_cases/q2/04_segmentBlocked. Each test file says what it checks and why.

Question 3 (5 points): Nearest Node

Implement RRTNode.findNearest(config): the node in the subtree rooted at self (including self) nearest to config, and its distance. The distance from self is computed for you; recurse into the children and keep the best.

To test and debug your code, run:

python3.12 autograder.py -q q3

Question 4 (10 points): RRT

Implement growRRT(tree, config_space, goal_test, step_limits, max_edge): one iteration of RRT. Sample q_rand, find the nearest node, steer toward q_rand but no farther than max_edge to get q_new, and add q_new to the tree if the segment from the nearest node is valid. The docstring gives the three return cases.

The later tests run the whole rrt() loop in seeded random worlds, in two and three dimensions, with different step limits, and check the plan it returns: every action within the limits, every configuration legal, and the last one a goal. In these worlds the agent has a radius, so a configuration within that distance of a wall is illegal too. Otherwise a single step could cut through a corner between two legal configurations.

To test and debug your code, run:

python3.12 autograder.py -q q4

Now go play. In amongUs.py, the crewmate plans a path to one of the other crewmates and follows it, replanning when the plan runs out (the tree is orange, the plan green). In robotCook.py, press 's' to switch the planner from RRT* to plain RRT, then 'p' to plan to the current goal, or 'a' to let the robot cook on its own. The right panel draws the tree and the plan in configuration space.

Question 5 (7 points): Best Parent

RRT* connects a new configuration to the neighbor that gives it the lowest cost from the root, not just the nearest one. Implement RRTNode.findAllNear(config, radius), the list of nodes in the subtree within radius of config, and addConfigToBestParent(q_new, neighbors, step_limits, config_space), which tries every neighbor and attaches q_new to the best one (or returns None if none has a valid segment to q_new). RRTNode.getCostFromRoot is provided.

To test and debug your code, run:

python3.12 autograder.py -q q5

Question 6 (7 points): Rewire

Implement rewire(new_node, neighbors, step_limits, config_space): for each neighbor, if the path from the root through new_node to the neighbor is valid and cheaper than the neighbor's current cost, make new_node its parent with neighbor.updateParent. The right panel of the figure above is the test case.

To test and debug your code, run:

python3.12 autograder.py -q q6

Question 7 (8 points): RRT*

Implement growRRTStar(tree, config_space, goal_test, step_limits, max_edge, rewire_radius): growRRT with the two tricks. Sample and steer as before, find the neighbors within rewire_radius of q_new (and make sure the nearest node is among them), attach q_new to its best parent, and, if it is not a goal, rewire the neighborhood. rrt() computes rewire_radius for you, shrinking it as the tree grows.

One deliberate simplification: rrt() stops as soon as a new node passes the goal test, for RRT* just as for RRT. Full RRT* could keep going after finding the goal, sampling and rewiring until an iteration budget runs out, and the path to the goal would keep getting shorter (that is where its asymptotic optimality comes from). We choose to stop at the first goal so that both planners return a plan quickly; the rewiring RRT* has already done along the way is what makes its path cheaper.

The random-world tests use the same seeds as Question 4 and require your RRT* path to cost no more than ours (with a little slack). With the same samples, a correct RRT* builds the same tree we do.

To test and debug your code, run:

python3.12 autograder.py -q q7

Back in the games, 's' toggles between RRT and RRT* (the robot cook starts with RRT*, the crewmate with RRT). Try python3.12 robotCook.py --links 4: the arm has four joints, the configuration space has four dimensions, the right panel can only show a two-dimensional slice of it, and rrt.py plans in it unchanged.

Submission

python3.12 autograder.py

python3.12 autograder.py -q q3