An online method to allocate tasks to robots on a team during natural disaster scenarios

Teams of robots could help users to complete numerous tasks more rapidly and efficiently, as well as keeping human agents out of harm’s way during hazardous operations. In recent years, some studies have particularly explored the potential of robot swarms in assisting human agents during search-and-rescue missions; for instance, while seeking out survivors of natural disasters or delivering food and survival kits to them.

Researchers at University of Buffalo have recently developed a technique that could enhance the performance of robot teams during disaster response missions. This technique, introduced in a paper published in Elsevier’s journal Robotics and Autonomous Systems, is designed to allocate tasks to different robots in a team, so that they can complete missions most effectively.

“Over the past three to four years, we have been exploring unique ways to coordinate large teams of ground robots and drones for assisting in hazard mapping and search-and-rescue operations that are critical to emergency and disaster response applications,” Dr. Souma Chowdhury, one of the researchers who led the study, told Tech Xplore. “During these research explorations, we converged upon the need for an algorithm that can quickly (on the go) allocate tasks among robots in the team.”

When they reviewed previous research studies, the researchers found that very few of the existing methods for multi-robot task allocation were able to handle simultaneous tasks with strict time deadlines and adapt to new unexpected tasks that may arise during a mission, while also considering the flight range, payload capacity and onboard computing constraints of real-world robots. They thus set out to develop an approach that would successfully do all these things.

“A further objective of our study was to demonstrate the capabilities of this new method on an original flood response application, where a team of drones is employed to quickly deliver or drop survival kits at specified task locations during a simulated flood scenario over a 20×30 km² area,” Dr. Chowdhury said.

In their study, Dr. Chowdhury and his colleague Dr. Payam Ghassemi considered teams of robots and the tasks they are meant to complete as two distinct sets of data. This allowed them to reduce the task of allocating problems to them, so that it primarily entailed mapping or matching pairs of elements from these two sets (i.e., a robot in the team with the task it would complete). Essentially, at any point when the model is required to make a decision, it connects every idle robot in set 1 to one of the tasks remaining in set 2, via an “edge.”

“Our technique then uses an incentive function to weight these edges, with a higher weight indicating a higher relative affinity of a robot to undertake the task connected by the concerned edge,” Dr. Ghassemi, the other researcher involved in the study, said. “A weighted bigraph matching problem is then solved to produce a one-to-one mapping that yields the immediate next task to be assigned to each robot. By designing the incentive function to account for the robot’s global state, the robot’s state relative to a task and the remaining time to complete the task, our approach becomes uniquely cognizant of robot’s constraints and task deadlines.”

The technique has several advantages over alternative, existing optimization-based multi-robot task allocation methods. For instance, its execution times are significantly shorter, as it can make task allocation decisions within a few hundred milliseconds.

In addition to being faster than other existing methods, the researchers’ technique alleviates the need for synchronous decision-making among robots. This means that its functioning has a lower dependence on the communication networks connecting robots in a team.

Drs. Chowdhury and Ghassemi evaluated their technique in a series of tests. Remarkably, they found that it could complete the same percentage of tasks as general optimization-based methods that provide provably optimal solutions, yet its computing times were almost 1,000 times lower.

“This observation, along with our technique’s ability to make asynchronous decisions, implies that our method could be readily implemented on widely available and inexpensive ground robots and drones,” Dr. Chowdhury said. “Such simple robots usually present frugal computing and communication capabilities.”

Interestingly, the researchers showed that their method can also be scaled up to tackle highly complex problems that involve teams with up to 100 robots that are meant to complete 1,000 tasks, while retaining its sub-second computing time performance. So far, very few teams have tried to tackle these large-scale problems using existing task allocation tools.

“The outcome of our study represents an important step forward for the multi-robotics community in terms of providing tangible evidence for the vision that very large and scalable teams of robots could revolutionize disaster response and other time sensitive operations,” Dr. Chowdhury said. “Lastly, by directly considering the realities of robot’s range and payload constraints, task deadlines and appearance of new tasks on the go (the latter are ubiquitous to disaster response operations), our findings take us closer to transitioning multi-robot task allocation algorithms to practice in complex large-scale operations.”

In the future, the online multi-robot task allocation technique developed by this team of researchers could facilitate the large-scale deployment of drone swarms or other robot teams during complex search and rescue missions. Meanwhile, Drs. Chowdhury and Ghassemi plan to conduct further experiments to evaluate their algorithm in more realistic simulations, created using contemporary gaming engines. This could finally allow them to deploy and test their technique on real teams of drones and four-wheeled ground robots.

“The University at Buffalo, School of Engineering and Applied Sciences, has recently unveiled a massive state-of-the-art outdoor drone testing facility, which would be a perfect setting for conducting these experiments in real-world conditions,” Dr. Chowdhury added. “On a more fundamental level, we plan to alleviate the need for handcrafting the incentive function for different types of operations and robots, and further minimize inter-robot communication needs. To this end, under a new research grant from the National Science Foundation, we are exploring how machine learning approaches can be used to learn incentive functions that will allow our algorithm to generalize over a wide range of real-world scenarios with minimal human inputs.”

© 2021 Science X Network