From: Stefan B. Sigurdsson (stebbi_at_cs.washington.edu)
Date: Tue May 13 2003 - 13:11:08 PDT
Agent-centered search
Sven Koenig
Summary - Agent-centered search is a planning paradigm that interleaves plan generation and execution, such that an incomplete plan is generated and executed and the plan generation phase is entered again before a goal is achieved. This paper surveys techniques for agent-centered planning in various domains, including domains with temporal constraints and uncertainty.
Key ideas
- The LRTA* algorithm described in the paper associates a heuristic value with each state that has been visited. It first selects a local search space, then updates the state values for the local search space, then selects an action to get out of the local search space, then executes, repeats until a goal state is reached.
- The planner moves downhill in the state value space but increments the state values to mark visited states. This supports escape from local minimas and eventual exploration of the entire state space if the goal isn't reached sooner.
- A richer utility model than standard goal attainment seems required, because plan generation and execution is interleaved to the extent that plan fragments are executed without achieving any concrete goals. Of course discovery and map-building fit this very well. I didn't read carefully enough to get a clear picture of how state values and rich utility models interact.
- The computational cost of generating a plan is alleviated because (a) execution starts before a complete plan has been derived and (b) interleaved execution helps narrowing down the search.
- Agent-centered search seems well-suited to a variety of interesting domains with uncertainty, very large search spaces, sensing, etc. The main drawback is that since actions are executed with imperfect knowledge and plans, mistakes may occur and it may not be possible to recover.
Questions
- How frequent/interesting are domains where there are no straightforward paths to the goals? In these cases, how well does the paradigm do? For example, I find that in most things I do I can make things up as I go, but both programming and research require more careful planning ahead...
Directions
- What's the state of the art in utility functions for short plans that don't achieve an end goal? Are there generic approaches? The paper may discuss this, if so then I skimmed past.
- Could some kind of preprocessing step be used to better/more intelligently initialize the LRTA* state values? Does this have to be domain-specific?
This archive was generated by hypermail 2.1.6 : Tue May 13 2003 - 13:11:09 PDT