Project3: Evaluation of
planning
algorithms in the Rescue domain
General:
Path
planning is a basic functionality for every Rescue agent. In the
discretized setting of the RobocupRescue simulation, efficient AI
search techniques can be used to find paths from an agent's current
position to a goal. However, the problem is complicated by the
partial observability in the Rescue domain: while the road net of a
city can be assumed to be fully known to each agent, the state of the
roads (blockades) is not. On the other hand, the continuousness of the
problems solved can be exploited:
knowledge gained from past cycles of planning and plan execution
(moving) can be reused.
Part I -
Evaluation of heuristic search techniques
Function:
There are several heuristic search techniques that can be used in
realistic settings where planning is continously interleaved with
execution. Implement a general heuristic search engine in which some
(or all) of the following methods can be plugged in: A*, Weighted A*
(WA*), RTA*, LRTA* and variants of these algorithms. For partial
observability planning you can consider techniques like Real-time
Dynamic Programming (RTDP), AO*, LAO* and HDP.
Evaluate these search methods in the RoboCupRescue domain. You should
compare the algorithms helpfulness both in offline
pre-processing of a map (during the first cycles of the
simulation) and online
(while acting in the simulation).
Approach:
Heuristic search. Dynamic programming
Literature:
J.
Pearl. Heuristics: Intelligent
Search Strategies for Computer Problem Solving. Addison-Wesley,
1984.
S. Koenig. Agent-Centered Search.
Artificial Intelligence Magazine, 22, (4), 109-131, 2001.
S. Koenig, D. Furcy and Colin
Bauer. Heuristic Search-Based Replanning. In Proceedings of the International
Conference on Artificial Intelligence Planning and Scheduling, 2002.
Andrew G. Barto,
Steven J. Bradtke, Satinder P. Singh: Learning to Act using Real-Time
Dynamic Programming, Artificial
Intelligence 72:
81–138. 1995
Blai Bonet and Hector Geffner. Faster Heuristic Search Algorithms
for Planning with Uncertainty and Full Feedback.
Proceedings of IJCAI-03.
Implementation:
The search engine can be
implemented following the general GRAPH-SEARCH procedure of
Russel/Norvig: AI - a Modern Approach, 2n ed., 2003.
Institut für
Informatik, Universität
Freiburg