Planning in a Multi-Agent Environment: Theory and Practice
抄録
We give the theoretical foundations and empirical evaluation of a
planning agent, SHOP, performing \htn planning in a multi-agent
environment. SHOP is based on \ashop, an agentized version of the original
SHOP \htn planning algorithm, and is integrated in the IMPACT multi-agent
environment. We ran several experiments involving accessing various
distributed, heterogeneous information sources, based on simplified versions
of noncombatant evacuation operations, NEO's. As a result, we noticed that
in such realistic settings the time spent on communication (including
network time) is orders of magnitude higher than the actual inference
process. This has important consequences for optimizations of such
planners. Our main results are: (1) using NEO's as new, more realistic
benchmarks for planners acting in an agent environment, and (2) a
memoization mechanism implemented on top of SHOP, which improves the
overall performance a lot.
(Also UMIACS-TR-2002-13)