ZENO and Nondeterministic Choices

In the description of the ZENO algorithm, there is an interesting point (that didn't come up for discussion in class today), which we have covered earlier in the semester. While describing the nondeterministic decisions in the algorithm, the authors list 3 points: decomposing complex goals, choosing actions, and introducing constraints to prevent interference. They then go on to state that completeness requires backtracking on these decisions. That is, just finding a satisficing solution can only be guaranteed if the "nondeterministic" choices are determinised.

However (and this they point out subsequently), we have already seen earlier that for plan-space planners, the order in which the subgoals are selected for satisfaction has no effect on completeness. That is, unless we want to find the optimal solution, we need not determinise (introduce backtrack into) the order in which goals are selected.

This raises some interesting points:

1. Could this dichotomy be seen as a manifestation of the fact that while it is true that *all* subgoals need to be satisfied (at least in non-PSP scenarios) to have *a* solution, a given solution need not contain *all* the possible decompositions, or actions, or constraints?

2. The second part of 1. can perhaps be stated better as follows: any given combination of actions, simple goals and constraints is not necessarily a subset of any given solution, for all solutions in the spaces; however, any given subset of the subgoals is *necessarily* a subset of the subgoal set needed for top-level goal achievement.

These are just some of the things I could think of; I thought this was a very interesting point put forward by the authors. Please feel free to add your own.

kartik