New research examines multi-agent task planning in open environments

Sep 19, 2019      By Victoria Grdina

Leen-Kiat Soh. Photo courtesy of Nebraska Today.
Leen-Kiat Soh. Photo courtesy of Nebraska Today.

Computer Science and Engineering professor Leen-Kiat Soh has earned a new grant to continue research that could revolutionize task and resource management systems in a wide variety of fields.  

The grant, with an overall budget of $498,391, titled “RI: Small: Collaborative Research: Scalable Decentralized Planning in Open Multi-Agent Environments,” is funded by the National Science Foundation’s Division of Information and Intelligent Systems (IIS)’s core program. Soh will conduct his research with Professor Adam Eck of Oberlin College (also a CSE Ph.D. graduate) and Professor Prashant Doshi of the University of Georgia. 

The ultimate goal of the project is to develop automated planning solutions that are capable of determining the optimal sequence of actions necessary to maximize rewards. These solutions would analyze real-life scenarios in complex environments—such as wildfire fighting or Uber ride hailing—that included multiple actors, tasks, and outcomes in uncertain and open environments with no or limited communication among actors. 

“If there are multiple actors with different ways of doing things in a stochastic and dynamic environment, how does an actor anticipate what others are going to do, without communication?” Soh said. “And then how does the same actor plan so that it reaches optimality over time?”

Soh explains that while several solutions have been reported to address these challenges, they’re only capable of analyzing closed environments where the sets of agents and tasks are fixed. Consequently, results are limited and not readily applicable to real-world scenarios. Soh’s research uniquely examines openenvironments, where agents and tasks may enter or exit an environment. 

In the case of Uber ride hailing, both drivers and customers may enter and exit a designated area, which affects the ride routes, income, choices, and actions of all agents in the situation. Optimal sequences need to be remodified depending on the actions of others. The possible results and effects are seemingly infinite. 

“Existing solutions in the literature are not scalable, due to large numbers of states, actions, and agents to explore,” Soh said. “We want to develop algorithms that are computationally viable and scalable.”

The project team’s proposed solution is another unique facet of the research project: statistical sampling. 

“If there are a thousand agents, instead of having to anticipate what the other 999 agents are going to do, maybe an agent only has to worry about a handful of them,” Soh said. “Sometimes we don’t need to worry about who the actors are, just how many actors there are. With firefighting, for example, it doesn’t matter which firefighters are acting, just how many it takes to put out the fire.”

Not only will this statistical sampling make solution development possible, but it will also allow Soh and his team to tap into an area of previously unexplored research.  

“Up to now in this kind of dynamic environment, the highest number of agents considered by existing solutions in terms of achieving consistent computational results has only been in the dozens,” Soh added. “We want to do thousands.”