Integrating Behavior Trees and Auction Theory for Multi-Agent Coordination

Monday - May 22 2023, 06:20 UTC - 1 year ago

Researchers at Lulea University of Technology in Sweden recently introduced a new multi-agent coordination method that integrates an auction-based task with behavior trees, mathematical models often used in computer science to execute plans. This method effectively organizes the actions of multiple robots who are working to achieve a common goal, allowing them to coordinate their efforts. The multi-agent coordination architecture proposed by this team of researchers could have notable advantages over other models proposed in the past that typically rely only on auction theory or behavior teams.

When tackling missions as a team, robots should be able to coordinate their efforts, for instance, completing different sub-tasks, monitoring different parts of a target environment, and so on. Over the past few years, computer scientists have therefore been developing computational models designed to coordinate the actions and behaviors of different robots in a team.Researchers at Lulea University of Technology in Sweden recently introduced a new multi-agent coordination method that integrates an auction-based task with behavior trees, mathematical models often used in computer science to execute plans. This method, introduced in a paper pre-published on arXiv, was found to effectively organize the actions of multiple robots who are working to achieve a common goal, particularly when they are completing tasks that span different stages.

"We found a need for a flexible and reactive task allocation architecture for coordinating multi-agent systems," Niklas Dahlquist, one of the researchers who carried out the study, told Tech Xplore. "I have previously worked with behavior trees and that's why I thought that combining them with a task allocation scheme could result in a flexible framework that also allows for easy integration of new types of tasks and different agents." .

The architecture developed by Dahlquist and his colleagues is based on a market-based approach, which underpins the functioning of auctions. Essentially, individual robotic agents in a team estimate the cost related to tackling different sub-tasks that need to be completed, placing "bids" through a central auctioning system. Subsequently, this auctioning system analyzes these "bids" and assigns optimal tasks to each of the agents.

"Our architecture also has a local layer, consisting of a behavior tree, that guides the individual agents to complete an allocated task," Dahlquist explained. "This gives the advantage that there is no need for a centralized unit to have full global knowledge about the system, all that is needed are the bids from the agents and also it reduces the computational burden." .

The multi-agent coordination architecture proposed by this team of researchers could have notable advantages over other models proposed in the past that typically rely only on auction theory or behavior teams. By separating task allocation and execution steps, for instance, this approach could be easier to apply to teams that contain robotic agents with different capabilities or to missions that entail very different sub-tasks.

"The most notable takeaway from this work is the integration of behavior trees with the task allocation to allow for incorporating multi-stage tasks," Dahlquist said. "This gives a flexible and scalable architecture for tackling scenarios where the specific tasks are unknown in advance." .

Dalquist and his colleagues evaluated their architecture in a series of experiments in their laboratory, using several TurtleBot3 robots. Their findings were very promising, as their method could coordinate the efforts of these robots while they were collectively tackling simple missions.

In the future, this new architecture could be applied in other scenarios, such as tasks in robot search and rescue, environmental monitoring or factory automation.