Adaptive Constraint-Based Agents in Artificial Environments

[THE NEARBY WIZARD]   [Bounds]   [Efficiency]   [Complexity]

[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

A Question of Efficiency

(Related publications: [PUBLink] [PUBLink])

«The wrong approach taken by your planning system,» the wizard starts to explain, «is due to its focusing on qualitative problems, like the ancient blocks-world domain. The only feature distinguishing solutions was the plan length, and so everyone wanted to optimize this. A systematic exploration of the search space along an increasing plan length is an obvious way of tackling this problem, and such approaches are still at the heart of today's planning systems, even if the problems now involve optimization criteria that do not change strictly monotonically with the plan length.»

In response to your questioningly look, he continues: «Your planning system has a very strange way of exploring the search space.» He draws a small figure on the ground (see figure below).

«The plan-length optimization of your system,» the wizard explains, «tries to verify that there is no valid solution for a certain plan length, and has to perform a complete search for this length before being able to increase the plan length. And even if you instruct it to begin with a certain length bound, it constructs the structures for the whole search space for this length, which is a pretty useless approach for non-toy problems.

As you have already realized, the plan-length criterion is a poor guide for the search because it has absolutely no relevance, so the search is rather like a random search. It is much more convenient to explore the search space without being bound to the plan length, as my planning system does. This allows us to perform a goal-property-driven search by integrating domain knowledge. Searching in an infinite search space means relying on powerful heuristics instead of being tied to a method of exploration that is determined by an irrelevant criterion.»

[THE NEARBY WIZARD]   [Bounds]   [Efficiency]   [Complexity]

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek