1 
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.

4

1 回答 1

1

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'.

于 2015-11-29T22:26:28.620 回答