RI: Small: Collaborative Research: Scalable Decentralized Planning in Open Multiagent Environments

University Of Nebraska-Lincoln, Lincoln NE

Investigators

Abstract

Automated planning is about finding a sequence of actions that is anticipated to successfully complete the task at hand or maximize earned rewards. Planning becomes difficult when the outcomes of actions are uncertain. It is further complicated in the presence of other agents whose actions also affect the environment and reward outcomes. While both these challenges have received much attention from researchers, real-world contexts often exhibit another property -- that of agent and task openness. Agent openness comes about when agents exit the environment, resume, or new agents enter, and task openness occurs when the tasks that agents must complete change with new tasks appearing and some disappearing. Such openness complicates the planning process as agents now need to optimally consider, for example, the possibilities of existing teammates leaving the environment or a successfully rewarding task disappearing from the environment. The research is systematically generalizing automated planning to consider these new and practical challenges while still keeping the methods computationally feasible. This research involves investigators at Oberlin College (a primarily undergraduate institution), Universities of Nebraska and Georgia collaborating closely to develop methods for planning in open multi-agent systems and demonstrating them in domains such as wildfire suppression, dynamic ridesharing, and others that exhibit openness. The principal investigators are using the outcomes of this research to inform their classroom instructions, and artificial intelligence camps for elementary and middle school students are planned at Oberlin. The technical approach involves gaining a fundamental understanding of the impact of agent and task openness on the environment, and utilizing this understanding to develop and learn stochastic models that represent the openness. These models are being used to build new algorithms for tractable agent-level planning in such contexts. The methods will exploit system-level properties such as agent anonymity and statistical population sampling that allows modeling large populations from small samples, which has been successful in the social sciences to make the approaches scalable to many agents. This research is advancing our understanding of how intelligent agents should perform scalable, decentralized planning in complex environments, and developing a framework--with empirical results and insights--that could lead to more robust intelligence for personal assistant agents for human-agent interactions, robots, and autonomous vehicles, where the agents reason about challenging environmental dynamics as the actors and their tasks change over time. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.