From: Tal Shaked (tshaked_at_u.washington.edu)
Date: Tue May 13 2003 - 08:23:57 PDT
Agent-Centered Search – Koenig
This article discusses agent-centered search methods that involve
interleaving planning with execution, with the idea of improving an agent’s
ability to construct and execute plans in a timely and efficient manner (the
definitions of which may depend on the specific domain or problem).
The main idea of this paper seems to be taking LRTA* (learning real-time
A* - which allows an agent to plan locally and then execute and learn from
it’s new state), and describing how the ideas can and have been extended to
a variety of domains such as deterministic, non-deterministic, and
uncertainty (various MDPs). The basic idea is that an agent can plan
locally (minimal being just its current state, and maximal being all known
states (such as visited)), and then update the heuristics for each state as
it progresses. This may speed up total planning plus execution time at the
loss of an optimal plan, but over time if it repeatedly solves the problem
it may reach an optimal solution.
The exploration of the various domains leads to several modifications and
cases to consider for the general LRTA*. For example, in known domains, but
uncertainty about the initial location, Min-Max LRTA* is described where the
idea is to find a worst case cost by having nature choose the worst branch
after each action considered (given all the possible states). Another point
mentioned is that a danger of interleaving planning with execution is to
avoid irreversible actions as well as cycling (guaranteeing progress in some
form such as information gain).
Maybe it was just my focus draining as the paper dragged on, but it seemed
that at first the paper was quite clear with good examples, and then as it
progressed, points became more general and abstract, and instead of going
into concrete examples, many pieces of work were cited as illustrating that
the methods worked.
An area to explore with agent-centered search is domains with incomplete and
unbounded information such as the Internet or Unix. Actually the paper
describes many areas that these ideas can be implemented and tested, such as
multiple agents each searching locally and sharing what they learn, which
could have many interesting applications such as quickly mapping domains or
searching for items.
This archive was generated by hypermail 2.1.6 : Tue May 13 2003 - 08:24:16 PDT