Planning with meta-actions

Intelligent Systems for Robotics · Week 7

Syllabus · Home

Week 6 gave the planner six skills and let it put them in order. This week you give it a seventh action that is six skills in a fixed order. You author that composition in the knowledge graph, derive its preconditions and effects from the steps rather than declaring them, hand it to the planner as one more action, and measure what changes. Week 6 varied the search with the domain fixed. This week varies the domain with the search fixed.

Objectives

Where week 6 left off

The fetch domain holds six plannable skills. navigate-to drives a route, place-base-for parks the base where the arm can reach, reach-to moves the arm, grasp closes the gripper, release opens it, and hand-over gives the object to a person. Each is a STRIPS operator with preconditions, an add list and a delete list (Fikes and Nilsson, 1971, section 3.2), written as a PDDL action by the generator you built. Poole and Mackworth, section 6.1, is where to revise that. Every derivation this week is worked from these six declarations, as isfr/skills/catalogue.py holds them.

SkillPreconditionsAddsDeletes
navigate-to ?from ?to(at ?from), (reachable ?from ?to)(at ?to)(at ?from), (base-placed), (arm-placed)
place-base-for ?obj ?place(at ?place), (object-at ?obj ?place)(base-placed-for ?obj), (base-placed)
reach-to ?obj(base-placed-for ?obj), (base-placed), (gripper-empty)(gripper-at ?obj), (arm-placed)
grasp ?obj ?place(gripper-at ?obj), (arm-placed), (gripper-empty), (at ?place), (object-at ?obj ?place)(holding ?obj)(gripper-empty), (gripper-at ?obj), (base-placed-for ?obj), (object-at ?obj ?place)
release ?obj(holding ?obj)(gripper-empty)(holding ?obj)
hand-over ?obj ?person ?place(holding ?obj), (at ?place), (person-at ?person ?place)(has ?person ?obj), (gripper-empty)(holding ?obj)

Four rows differ from week 6. They use two new atoms with no arguments, (base-placed) and (arm-placed). place-base-for adds (base-placed) and reach-to needs it. reach-to adds (arm-placed) and grasp needs it. navigate-to deletes both, because a base that drives away is no longer placed and neither is its arm. Without these atoms the planner reached for a drink, drove away and back, and grasped it, a plan no robot can carry out. Now a plan grasps where it placed the base, except at a place holding two drinks. Your week 6 generator needs no change to use the new declaration.

Task a of the micro-project asks for one drink delivered to one person. Task d asks for two. Both are solved from the same domain and from the apartment's map and belief graph. Here is what the flat domain costs on those two tasks, under the two Fast Downward configurations of this week.

TaskEnginePlan lengthExpansions
afast-downward-opt69
afast-downward711
dfast-downward-opt1253
dfast-downward1333

The optimal engine returns six steps on task a and twelve on task d. The satisficing engine returns seven and thirteen, since it guarantees nothing about length. Week 6 measured blind search on the same pair of tasks, and watched its expansions grow sharply from one drink to two. The heuristic engines above do far better, and the second task still costs more than the first.

Both engines are Fast Downward. pyperplan, three of week 6's four configurations, is absent, because its PDDL parser rejects the (:functions (total-cost)) declaration that this week's action costs need.

Look at the six steps of task a's optimal plan. The robot drives to the drink, places the base, reaches, grasps, drives to the person, and hands over. Those six steps are not six independent choices. Once the planner has committed to fetching a particular drink for a particular person, the order of the six is forced by their preconditions. The planner rediscovers that order on every task, and task d pays for it twice. A meta-action is a way of writing the order down once.

What a meta-action is

A meta-action is a composition of skills, authored in the knowledge graph, fixed in length, whose preconditions and effects are derived from its steps and never declared (D3). It is one more action in the planning domain.

It lives in the graph, in the same Turtle files as the map and the beliefs. A meta-action node carries an rdfs:label, a set of isfr:parameter nodes and a set of isfr:step nodes. Turtle has no order, so each parameter carries an isfr:parameterIndex and each step an isfr:stepIndex, and the loader sorts on those. A parameter also carries an isfr:variable, which is the name the steps use, and an isfr:parameterClass, which is the ontology class its argument must belong to. A step carries an isfr:call, which is one skill name and its arguments in PDDL shape.

This week's meta-action is fetch. It has five parameters.

IndexVariableisfr:parameterClass
0?fromisfr:Place
1?srcisfr:Place
2?drinkisfr:Drink
3?dstisfr:Place
4?personisfr:Person

When the generator writes fetch as a PDDL action, its parameter types come from the graph. A skill's parameter is typed by its name, since in the catalogue obj is always a drink and from, to and place are always places. A meta-action's parameters are named by whoever authors it, so that table cannot type them, and isfr:parameterClass does the work instead.

isfr:parameterClassPDDL type
isfr:Placeplace
isfr:Drinkdrink
isfr:Containerdrink
isfr:Personperson

A parameter with no class, or with a class outside that table, is an error that names the meta-action and the variable. The problem builder already treats any grounded container as a drink, which is why isfr:Container maps to drink.

And six steps, in this order.

0  (navigate-to ?from ?src)
1  (place-base-for ?drink ?src)
2  (reach-to ?drink)
3  (grasp ?drink ?src)
4  (navigate-to ?src ?dst)
5  (hand-over ?drink ?person ?dst)

Every variable a step uses is one of the five parameters. That is the first rule the validator enforces. A step that mentioned ?place, which is no parameter of fetch, would be rejected, because nothing in the domain could bind it. The second rule is that every step calls a registered skill, with as many arguments as that skill takes. A third rule arrives with nesting.

A meta-action is not a task the planner breaks open during search, and it is not a task the robot breaks open while it runs. Its steps are decided when it is authored and they never change. That is what separates it from a hierarchical task network. An HTN planner is given tasks and methods for decomposing them, and it chooses a decomposition during the search, so the length of what a task turns into is decided while planning. Poole and Mackworth name the HTN approach in one sentence in section 6.8 and point at a book for it. The course goes no further.

The length is fixed because the planner needs a single action with a single annotation. A composition that could be any length would need its preconditions worked out during the search, for each length, which is a second planner inside the first. Fixing the length means the preconditions and effects can be computed once, when the graph is loaded, and from then on fetch is an action like any other. The price is that fetch fetches one drink for one person and nothing else. Two deliveries take two fetch steps, which is what task d shows.

Deriving the annotations

A meta-action declares no preconditions and no effects. They are derived from the steps, and the derivation is the whole of part 1 of this week's micro-project.

Why nothing is declared

The third rule of D3 is that a meta-action's preconditions and effects are always derived and never declared. A meta-action that states a precondition of its own is rejected by the loader before your derive ever sees it.

The reason is that two sources of truth can disagree. If an author could declare the annotation and also give the steps, then an edit to a step would leave a stale declaration behind, and the planner would reason about a meta-action that no longer matches what the robot would do. Deriving makes the steps the only thing an author can get wrong.

The rule is enforced in the loader rather than in your validate, because the type your derive returns has no field for a declaration. The loader is the last place that sees the graph itself.

The walk

The derivation is a walk. You go through the steps in index order and keep two sets, the atoms earlier steps have made true and the atoms earlier steps have made false. Both start empty. For each precondition of each step, there are three cases.

Then the step's own effects update the two sets. An effect that makes an atom true adds it to the made-true set and removes it from the made-false set. An effect that makes an atom false does the reverse. Within one step the deletes apply first, which is the rule week 6 took from Fox and Long (2003), Definition 13, section 7.1:

$$s' = (s \setminus \mathit{Del}(a)) \cup \mathit{Add}(a)$$

The order decides the outcome whenever one atom is on both lists of one step. Applying the adds first and the deletes afterwards would leave such an atom false, and the derivation would disagree with every planner that reads the same domain.

At the end, the made-true set gives the positive effects of the meta-action and the made-false set gives the negated ones. The preconditions collected along the way, as a set, are the preconditions of the whole.

fetch, derived by hand

Run the walk over fetch's six steps, reading each skill's declaration from the table in the first section. The third column below is what each step adds to the meta-action's preconditions.

StepCallNew precondition of the wholeAlready supplied inside
0 (navigate-to ?from ?src) (at ?from), (reachable ?from ?src) nothing yet
1 (place-base-for ?drink ?src) (object-at ?drink ?src) (at ?src), from step 0
2 (reach-to ?drink) (gripper-empty) (base-placed-for ?drink) and (base-placed), from step 1
3 (grasp ?drink ?src) none (gripper-at ?drink) and (arm-placed) from step 2, and (at ?src) from step 0; (gripper-empty) and (object-at ?drink ?src) are already required
4 (navigate-to ?src ?dst) (reachable ?src ?dst) (at ?src), from step 0
5 (hand-over ?drink ?person ?dst) (person-at ?person ?dst) (holding ?drink) from step 3, (at ?dst) from step 4

Step 3 is the one to read twice. grasp has five preconditions and not one of them is new. Three were established inside the meta-action, and two were already collected at earlier steps, so asking for them again changes nothing. Preconditions form a set, and a set does not care how often an atom is put into it.

Here is the same walk seen through the two effect sets, after each step. Note that step 0 puts (base-placed) and (arm-placed) into the made-false set before either was ever true, since navigate-to deletes both.

After stepMade trueMade false
0 (at ?src) (at ?from), (base-placed), (arm-placed)
1 (at ?src), (base-placed-for ?drink), (base-placed) (at ?from), (arm-placed)
2 (at ?src), (base-placed-for ?drink), (base-placed), (gripper-at ?drink), (arm-placed) (at ?from)
3 (at ?src), (base-placed), (arm-placed), (holding ?drink) (at ?from), (gripper-empty), (gripper-at ?drink), (base-placed-for ?drink), (object-at ?drink ?src)
4 (holding ?drink), (at ?dst) (at ?from), (gripper-empty), (gripper-at ?drink), (base-placed-for ?drink), (object-at ?drink ?src), (at ?src), (base-placed), (arm-placed)
5 (at ?dst), (has ?person ?drink), (gripper-empty) (at ?from), (gripper-at ?drink), (base-placed-for ?drink), (object-at ?drink ?src), (at ?src), (base-placed), (arm-placed), (holding ?drink)

Watch (gripper-empty) cross the table. Step 3 makes it false, because grasp deletes it. Step 5 makes it true again, because hand-over ends by letting go, and that effect removes the atom from the made-false set. At the end (gripper-empty) is a positive effect of fetch and also one of its preconditions. The gripper must be empty before fetch starts and it is empty again when fetch finishes.

Watch (at ?src) as well. Step 0 makes it true, step 4 makes it false, and the final sets hold it only as a negated effect. The ledger holds the last word on each atom rather than its history.

So the derivation gives fetch six preconditions:

(at ?from)   (reachable ?from ?src)   (object-at ?drink ?src)
(gripper-empty)   (reachable ?src ?dst)   (person-at ?person ?dst)

And eleven effects, three positive and eight negated:

(at ?dst)   (has ?person ?drink)   (gripper-empty)
(not (at ?from))   (not (gripper-at ?drink))   (not (base-placed-for ?drink))
(not (object-at ?drink ?src))   (not (at ?src))   (not (base-placed))
(not (arm-placed))   (not (holding ?drink))

Six and eleven are the numbers to check your own derivation against. Nothing about them was chosen. They follow from the six skill declarations and the order of the steps.

When the derivation rejects

The micro-project ships a second meta-action, grasp-twice, with two parameters and two steps that are both (grasp ?obj ?place). You leave it as it is. A correct derivation rejects it, and that rejection is the first thing your code has to get right.

Walk it. Step 0 is grasp, and none of its five preconditions is supplied by an earlier step, so all five become preconditions of the whole: (gripper-at ?obj), (arm-placed), (gripper-empty), (at ?place) and (object-at ?obj ?place). Then step 0's effects run. It makes (holding ?obj) true, and it makes (gripper-empty), (gripper-at ?obj), (base-placed-for ?obj) and (object-at ?obj ?place) false.

Step 1 is the same grasp. Its first precondition is (gripper-at ?obj), which is in the made-false set. The gripper was at the object, the grasp closed on it, and the skill declares that it is no longer merely at it. Nothing between the two steps puts it back. The composition is rejected, and the report names the step and the atom.

grasp-twice: rejected: grasp-twice: step 1 (grasp ?obj ?place)
needs (gripper-at ?obj), which an earlier step made false

(gripper-empty) is false at that point too, and so is (object-at ?obj ?place). One failed precondition is enough to reject, so which one your walk reports depends on the order you check them in. What matters is that the rejection happens at all.

A rejected meta-action is caught when the graph is loaded, which is before any planning and long before any driving. That is the evidence for deriving rather than declaring. An author who had written the preconditions of grasp-twice by hand would have written something plausible, the planner would have used it, and the robot would have discovered the problem by trying to grasp an object it was already holding.

What the derivation exposed in grasp

That argument is not hypothetical here. When fetch was first derived for this course, grasp took one parameter and deleted one atom, (gripper-empty). The walk over the six steps then left (gripper-at ?drink) and (base-placed-for ?drink) among fetch's positive effects, and never touched (object-at ?drink ?src) at all. Read as an annotation, that says the drink is still on the worktop after the robot has carried it across the apartment and handed it over, with the gripper still at it and the base still parked for it.

Those three atoms were annotations a person had written by hand on grasp, and they were wrong. The outcome was that grasp gained a ?place parameter, so grasp(?obj ?place) now deletes (gripper-at ?obj), (base-placed-for ?obj) and (object-at ?obj ?place). Without a place, the skill had no way to name the object-at atom it destroyed, and the other two deletes had been left out with it.

A skill's declaration is read one skill at a time, and nothing about grasp on its own looked wrong. A derivation reads six declarations in order and shows what the sequence leaves behind. So deriving saves you from writing an annotation for every composition, and it also checks the annotations you already wrote on the skills. The second of those is the larger half.

Binding and nesting

The derivation treats ?from, ?src and ?dst as three different things. A planner is under no such obligation. It binds each parameter to an object, and nothing stops it binding two of them to the same object. Distinct parameters that may later be bound back to one object are the normal state of affairs, and the last section shows that Shakey's authors met them in 1972.

Take ?from and ?src bound to one place, which is what happens when the robot already stands where the drink is. Derive fetch again with both replaced by ?p. The composition stays consistent. There are still six preconditions, and one of them is now (reachable ?p ?p). That holds, because week 6 made reachability reflexive, and the lecture notes of that week said this week was the reason. The effects fall from eleven to ten, since (not (at ?from)) and (not (at ?src)) are now the same atom.

Step 0 then drives from a place to itself, which costs the robot nothing. A reflexive navigate-to is harmless for the reason week 6 gave. Its add list is {(at ?p)}, its delete list holds (at ?p) as well, and the deletes apply first, so the robot stays where it was. The delete list also holds (base-placed) and (arm-placed), and steps 1 and 2 make both true again.

Nesting

A step may call another meta-action instead of a skill. That is what makes this a hierarchy and not a single flat layer, and it is why expansion is defined recursively. A meta-action that calls a meta-action expands to the inner one's steps, which expand in their turn, until nothing but registered skills is left.

The derivation needs the same recursion. To walk a step that calls a meta-action, you need that meta-action's own preconditions and effects, so you derive the inner one first.

So the validator has a third rule. If a calls b and b calls a, neither can be derived first, the expansion never terminates, and the recursion runs until the interpreter stops it. The validator checks that the calls between meta-actions form no cycle, and rejects the set when they do. A meta-action that calls itself is the shortest such cycle.

Meta-actions in the domain

A derived meta-action is a PDDL action and nothing more. Here is fetch as the generator writes it.

(:action fetch
  :parameters (?from - place ?src - place ?drink - drink ?dst - place ?person - person)
  :precondition (and (at ?from) (reachable ?from ?src) (object-at ?drink ?src)
                     (gripper-empty) (reachable ?src ?dst) (person-at ?person ?dst))
  :effect (and (at ?dst) (has ?person ?drink) (gripper-empty)
               (not (at ?from)) (not (gripper-at ?drink))
               (not (base-placed-for ?drink)) (not (object-at ?drink ?src))
               (not (at ?src)) (not (base-placed)) (not (arm-placed))
               (not (holding ?drink))))

Read it beside the release action of week 6 and there is no difference in kind. Same syntax, same predicates, same grounding. The planner has no way of telling that this action is six skills, and that is the point.

What an action costs

Every action in week 6's domain cost 1, because the generator set no metric. Leave it that way and fetch costs 1 against the six skills it replaces, so the macro domain wins on plan cost for a reason that has nothing to do with planning.

So a meta-action costs the number of primitive steps in its full expansion, and a skill costs 1. fetch costs 6. The macro problems carry a metric that minimises the total cost. The flat problems carry none, since every action in them costs 1 either way. fast-downward-opt honours the metric. For that engine the optimal cost of a task is the same with and without the macro, so the only thing the macro can change is the effort of finding a plan, which is what this week measures. This week's example shows what happens if you break the rule. Price its macro below the cost of its steps and the optimal engine returns a plan that costs less than any flat plan, because you have changed the problem rather than the search.

fast-downward runs Fast Downward's lama-first configuration. It reads the metric and then searches as if every action cost 1, so to it fetch is one cheap step whatever it replaces. Priced at 60 or 600 on task d, fetch stays in its plan, while fast-downward-opt drops it and returns the twelve-step flat plan. The satisficing engine's gain from the macro is a real measurement. It is gained under a different objective from the optimal engine's, so it is not the same fair comparison.

Expansion, before anything runs

A plan that holds fetch is not a plan the robot can run. The executive knows skills, and fetch is not one. So a plan is expanded before it is executed, and before it is replayed. Every meta-action is replaced by its own steps with the parameters bound, recursively, until only registered skills remain. One fetch becomes six skill calls with their arguments.

Expansion is also what makes the comparison honest. A one-step plan holding fetch is not less work than a six-step plan of skills, and a table that reported only the length as returned would say that it was. Every row of this week's table carries both the length as returned and the length after expansion.

Every expanded plan is then replayed against the skills' own preconditions and effects, step by step, deletes before adds. The replay checks the plan against the catalogue rather than against your derivation, which is what lets it catch a derivation that is too weak. A replay against your own annotations would check the plan against the very preconditions that let it through.

A wrong derivation shows up in one of three ways. The plan fails the replay, the plan is longer than it should be, or there is no plan at all. Which of the three you see depends on your derivation and on the engine, so do not expect every configuration to catch every mistake.

Does it pay

Here is the measurement, on the apartment's reference map and belief graph, on tasks a and d, under both engines, with and without fetch. The expanded column is the plan length after every meta-action is replaced by its steps. The expansions column is the number of search nodes the engine expanded. They count different things.

TaskEngineDomainLengthExpandedExpansions
afast-downward-optflat669
afast-downward-optmacro163
afast-downwardflat7711
afast-downwardmacro162
dfast-downward-optflat121253
dfast-downward-optmacro21222
dfast-downwardflat131333
dfast-downwardmacro2123

The macro domain expands fewer nodes in all four cells. Nine become three and fifty-three become twenty-two under the optimal engine, and eleven become two and thirty-three become three under the satisficing one. The satisficing engine's cut is the larger, likely because its search counts fetch as a single step of cost 1. The expanded lengths are equal under the optimal engine, 6 against 6 and 12 against 12, which is what the cost metric guarantees. Under the satisficing engine the macro plans are shorter once expanded, 6 against 7 and 12 against 13, because that engine's flat plans were not shortest to begin with.

The returned plan is one fetch on task a and two on task d, one per delivery. A meta-action of fixed length cannot do anything else.

The same macro, the opposite verdict

On the apartment, the macro cuts expansions under both engines. How far that result travels is a separate question, and this week's example answers it on a second domain. It runs the Gripper domain of week 6, flat and with carry-two, a macro that picks two balls, moves and drops them both.

At eleven balls, fast-downward-opt expands 161355 states with the macro and 161355 states without it. The macro buys that engine nothing at all. It costs about three times the wall clock, 3.97 s against 1.32 s, for the same search. The same macro helps fast-downward a great deal, at every number of balls the example reaches. At eleven balls, one macro and one domain give opposite verdicts under the two engines.

The likely mechanism is the one Botea and colleagues describe. A macro adds to a node's successor list states that would normally be reached in several steps, so it can reduce the maximal depth of a search, and it pays for that reduction with a larger branching factor (Botea et al., 2005, section 3.4.1). The two halves of that trade can be counted.

What the macro adds

Adding an action schema adds ground actions, one for each way of substituting objects of the right type for its parameters. Estimate first. Five parameters over the problem's places, drinks and people run to the order of $10^5$ substitutions, and that is the estimate this week started from.

Then measure. On the apartment problems, the flat domain grounds to 519 actions on task a and 526 on task d. fetch adds 154 on task a and 308 on task d. The measured counts are more than two orders of magnitude below the estimate, so the planner plainly does not keep every combination. Estimate the grounding of a schema and then measure it, because the two can disagree by that much.

Why the seconds are not in the table

The macro does not save time on the apartment. Every search in its table takes under 5 ms, and measured end to end the macro domain is slower than the flat one in all four cells. The likely reason is the grounding just counted. Building those ground actions costs more than the shorter search saves.

That is what a search of nine nodes looks like when you time it. Expansions are the honest measure of search effort at this size, because they are a property of the domain, the problem and the engine, and they come out the same on every machine. Seconds at this size are mostly the fixed cost of translating the problem before the search starts. Your own table will carry a seconds column, and the thing to read in it is whether the macro row is slower, not by how much.

Why the two domains differ

On the apartment the six steps of fetch are a chain the search would otherwise walk one step at a time, and fetch grounds narrowly, so the depth it removes is worth more in node expansions than the actions it adds. On Gripper the optimal engine's work is of another kind. It must prove that no cheaper plan exists, over a state space the macro does not shrink, and carry-two adds edges to that space without adding any shortcut through it, since going the long way costs exactly what the macro costs.

The utility problem

Minton (1988) gave this trade its name. The readable statement of it is his AAAI-88 paper, whose subject is search control rules in PRODIGY rather than macro-operators, and whose statement of the problem is general. Control knowledge has a hidden cost that can defeat its purpose, the cost of testing whether the knowledge applies as the search is carried out, so for the knowledge to improve efficiency its benefits must outweigh its costs. He names that the utility problem, and he reports that it is harder to improve performance over a population of examples than on isolated examples (Minton, 1988, page 564). PRODIGY measured each rule's utility as its average saving times how often it applied, minus its average matching cost, and discarded a rule whose utility turned out negative (page 567).

Mapping that onto a macro is this course's own step, and Botea, Enzenberger, Müller and Schaeffer (2005) make it for macros directly. The overhead of poor macros can outweigh their benefit, which they also call the utility problem, citing Minton; adding operators to a domain raises both the preprocessing cost and the cost per node in the search (section 2.2.2). If all instantiations of a macro are considered, the branching factor can increase significantly and the induced overhead can be larger than the savings achieved by the useful instantiations (section 3.3).

The question a meta-action has to answer is therefore a quantitative one. Is the depth it removes worth the ground actions it adds, for the engine you actually plan with, on the problems you actually solve? Being a sensible thing for a robot to do settles nothing, and fetch is plainly that. The engine also decides whether price can keep a poor macro out. fast-downward searches as if every action cost 1, so the price of a macro has no effect on whether that engine uses it. Both halves of the trade have to be measured. The second written question of the micro-project asks you to say when the answer is no.

Learned macros, and week 8

fetch is authored. Someone decided its six steps and wrote them into the graph. The alternative is to learn macros from plans the planner has already found, and that idea is as old as the walk you did to derive fetch.

That walk is older than PDDL. Fikes, Hart and Nilsson (1972), section 3, page 258, store a plan in a triangle table, a lower triangular array whose rows and columns correspond to the operators of the plan. Column i holds the add list of operator i at the top, and below it the part of that add list which survives each later operator, so cell (i, j) holds the clauses added by operator j that are still true when operator i applies. The union of the cells in the bottom row is the add list of the whole sequence (page 258). The left-most column holds a set of sufficient conditions for the applicability of the entire plan, and its conjunction is the plan's precondition formula (page 261). Page 260 puts the rule in one sentence. A tail of a plan applies to a model if the model already contains that portion of the support of each operator in the tail that is not supplied within the tail itself.

Nilsson (1990), section B, page 4, states it in four parts. The third is the walk's case of an atom in neither set, and the fourth is its made-false set.

Fikes, Hart and Nilsson (1972) did it for Shakey. A plan STRIPS had produced was stored as a triangle table, then generalised by section 4.2's procedure, which replaces every constant in the left-most column with a new parameter and constrains the lifted table so that each row still supports its operator's preconditions. Multiple occurrences of one constant become distinct parameters (page 262), which is the binding problem of ?from and ?src. The generalised plan was stored as a macro operator, a MACROP (section 4.3, page 268), and was available to later problems. Fikes and Nilsson (1993), pages 227 and 228, give their own account of that period. The Shakey work provided the context for A*, for STRIPS and ABSTRIPS, for programs generalising and learning macro-operators, and for triangle tables used in plan execution. Botea et al. (2005) is the modern form of the same idea, with macros learned automatically.

This course does not learn them. The thesis stated in week 1 is that only what classical methods do badly is learned, and the three things on that list are navigation, base placement and collision-free reaching. Composing skills is not on it. fetch is authored instead, which also means a person can say why its six steps are those six.

Next week the plan runs. A plan is a sequence of skill calls that the planner believed would have their declared effects, and on the robot any call can terminate in failure. Week 8 compiles a plan into a tree of guarded steps, checks each guard against the graph and the robot before the step runs, and replans when a step fails. That monitor has an ancestor too. PLANEX used triangle tables to monitor the execution of plans (Fikes, Hart and Nilsson, 1972, section 5.1, page 268), checking what was still true before it carried on. Week 8 checks the same thing in a different notation.

Slides

Deck for this week

Example

Run from the repository root:

PYTHONPATH=. python3 examples/07-planning-with-meta-actions/main.py

It plans the Gripper domain flat and with carry-two, under both Fast Downward configurations, for a growing number of balls, and prints the plan length, the expanded length, the states expanded and the seconds for each run. Pass --limit with a number of seconds to stop the table earlier or later. Nothing in it needs Webots, and it does not use the fetch domain. Read gripper.pddl and gripper-macro.pddl before main.py, and read the README's table beside your own run.

Micro-project

This week's exercise is exercises/07-planning-with-meta-actions/. Its README.md states the task and ends in a Self Check list you can verify unaided. The instructor's version is published in data/reference/week-07/ after the deadline.

Part 1 is the derivation. You write validate and derive, then author fetch in the graph with its five parameters and six steps, and check that grasp-twice is rejected and fetch derives to six and eleven. Part 2 hands your derived annotations to the provided generator, plans both tasks with and without fetch under both engines, replays every plan in expanded form, and fills a table. Three written questions follow it.

The micro-project runs from the inputs it provides. It does not need any earlier week's output.

Before week 8, run the example, read Fikes, Hart and Nilsson (1972), section 3, and finish part 1.

Reading

Further, optional, and not examined:

More background, optional: further reading.


Intelligent Systems for Robotics · course materials