SIFT Researcher's three papers accepted for publication and presentation at AAMAS-12
SIFT Researcher Dr. Ugur Kuter has recently collaborated with University of Maryland, College Park and Naval Research Labs at Washington DC. in a total of three papers on novel AI planning formalisms and algorithms in classical and dynamic, multi-agent domains. These works will be published and presented at the 11th International Conference on Autonomous Agents and Multiagent System (AAMAS-12).
V. Shivashankar, U. Kuter, D.Nau, and R. Alford. 2012. A Hierarchical Goal-Based Formalism and Algorithm for Single-Agent Planning.Proceedings of AAMAS-12.
Abstract: Plan generation is important in a number of agent applications, but such applications generally require elaborate domain models that include not only the definitions of the actions that an agent can perform in a given domain, but also information about the most effective ways to generate plans for the agent in that domain. Such models typically take a large amount of human effort to create. To alleviate this problem, we have developed a hierarchical goal-based planning formalism and a planning algorithm, GDP (Goal- Decomposition Planner), that combines some aspects of both HTN planning and domain-independent planning. For example, it allows the planning agent to use domain-independent heuristic functions to guide the application of both methods and actions. This paper describes the formalism, planning algorithm, correctness theorems, and the results of a large experimental study. The experiments show that our planning algorithm works as well as the well-known SHOP2 HTN planner, using domain models only about half the size of SHOP2’s.
M. Molineaux, U. Kuter, and M. Klenk. 2012. DiscoverHistory: Understanding the Past in Planning and Execution. Proceedings of AAMAS-12.
Abstract: We consider the problem of automated planning and control for an execution agent operating in environments that are partially- observable with deterministic exogenous events. We describe a new formalism and a new algorithm, DISCOVERHISTORY, that en- ables our agent, DHAgent, to proactively expand its knowledge of the environment during execution by forming explanations that re- veal information about the world. We describe how DHAgent uses this information to improve the projections made during planning. Finally, we present an ablation study that examines the impact of explanation generation on execution performance. The results of this study demonstrate that our approach significantly increases the goal achievement success rate of DHAgent against an ablated ver- sion that does not perform explanation.
E. Raboin, U. Kuter, and D.Nau. 2012. Generating Strategies for Multi-Agent Pursuit-Evasion Games in Partially Observable Euclidean Space. Proceedings of AAMAS-12.
Abstract: We present a heuristic search technique for multi-agent pursuit- evasion games in partially observable Euclidean space where a team of tracker agents attempt to minimize their uncertainty about an evasive target agent. Agents’ movement and observation capabili- ties are restricted by polygonal obstacles, while agents’ knowledge of each others’ location is limited to direct observation or periodic updates from team members. Our polynomial-time algorithm is able to generate strategies for games in continuous two-dimensional Euclidean space, an improve- ment over past algorithms that were only applicable to simple grid- world domains. We show experimentally that our algorithm is tol- erant of interruptions in communication between agents, continu- ing to generate good strategies despite long periods of time where agents are unable to communicate directly. Experimental results also show that our technique generates effective strategies quickly, with decision times of less than a second for reasonably sized domains with six or more agents.