Whether optimizing the fight against wildfires or minimizing the wait for a Lyft, the research of Leen-Kiat Soh could transform the management of tasks and resources across various fields.
With new grant support from the National Science Foundation, Soh is working to automate the sequencing of actions that can maximize rewards in scenarios involving multiple tasks and actors — particularly when those actors have limited or no communication.
“If there are multiple actors with different ways of doing things in a (random) and dynamic environment, how does an actor anticipate what others are going to do without communication?” said Soh, professor of computer science and engineering. “And then how does the same actor plan so that it reaches optimality over time?”
While multiple solutions have been proposed to address these challenges, Soh said, they’re capable of analyzing only environments in which the sets of agents and tasks are fixed. Consequently, results are limited and not readily applicable to real scenarios. Soh’s research instead examines open environments, where agents and tasks may enter or exit.
In the case of ride-hailing services, both the drivers and customers may enter and exit a designated area, affecting the routes, income, choices and actions of all agents. Optimal sequences need to be modified depending on the actions of others, Soh said, leading to a seemingly infinite set of outcomes.
“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 distinct 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.”
Statistical sampling could not only improve the quality of solutions but allow Soh and his colleagues, including Oberlin College’s Adam Eck and the University of Georgia’s Prashant Doshi, to tap into unexplored research areas.
“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 said. “We want to do thousands.”