Intelligent Systems for Robotics · Week 7
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.
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.
| Skill | Preconditions | Adds | Deletes |
|---|---|---|---|
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.
| Task | Engine | Plan length | Expansions |
|---|---|---|---|
| a | fast-downward-opt | 6 | 9 |
| a | fast-downward | 7 | 11 |
| d | fast-downward-opt | 12 | 53 |
| d | fast-downward | 13 | 33 |
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.
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.
| Index | Variable | isfr:parameterClass |
|---|---|---|
| 0 | ?from | isfr:Place |
| 1 | ?src | isfr:Place |
| 2 | ?drink | isfr:Drink |
| 3 | ?dst | isfr:Place |
| 4 | ?person | isfr: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:parameterClass | PDDL type |
|---|---|
isfr:Place | place |
isfr:Drink | drink |
isfr:Container | drink |
isfr:Person | person |
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.
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.
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 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.
| Step | Call | New precondition of the whole | Already 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 step | Made true | Made 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.
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.
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.
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.
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.
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.
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.
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.
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.
| Task | Engine | Domain | Length | Expanded | Expansions |
|---|---|---|---|---|---|
| a | fast-downward-opt | flat | 6 | 6 | 9 |
| a | fast-downward-opt | macro | 1 | 6 | 3 |
| a | fast-downward | flat | 7 | 7 | 11 |
| a | fast-downward | macro | 1 | 6 | 2 |
| d | fast-downward-opt | flat | 12 | 12 | 53 |
| d | fast-downward-opt | macro | 2 | 12 | 22 |
| d | fast-downward | flat | 13 | 13 | 33 |
| d | fast-downward | macro | 2 | 12 | 3 |
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.
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.
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.
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.
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.
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.
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.
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.
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.
Further, optional, and not examined:
More background, optional: further reading.
Intelligent Systems for Robotics · course materials