Input : Set of operators 0, Start state s, Goal state g
Output : Plan P
1. begin
2. | let P = [];
3. | while g (is not a subset of) s do
4. | | let E = {a|a is ground instance of an operator in O,
5. | | and Preconditions(a) hold in s}
6. | | if E = {} then
7. | | | return failure
8. | | end
9. | | choose a (which is a member of) E;
10. | | let s = s\ DeleteList(a) (union) AddList(a)
11. | | P = P @ [a]
12. | end
13. | return P
14.end
I'm struggling to understand lines 4,5 (and what is E used for?), lines 9 (how does it choose?) and line 10.
Thank you for any help you can offer.
E is the set of applicable operations in s. That is, E is the set of operations in O for which all of their preconditions hold in s.
If there are no such operations, this 'branch' of the planning algorithm results in a failure (lines 6 and 7) - no plan can be found from s to reach the goal state g.
Line 9 most likely means 'nondeterministically choose'; which is, in a very light and abstract sense, 'try all of them in parallel'. In practice, though, an implementation of a depth-first planner would most likely try members of E one-by-one*, deterministically.
Line 10 states that the next state is given by the removal of negative effects and the addition of the positive effects of the chosen operator a.
*which should require adaptations of the code to check for loops in order to guarantee completeness. See section 4.2.2 of Nau, Ghallab and Traverso's 'Automated Planning - Theory & Practice'.