Design for One, Deploy for Many: Navigating Tree Mazes with Multiple Agents
Maze-like environments, such as cave and pipe networks, pose unique challenges for multiple robots to coordinate, including communication constraints and congestion. To address these challenges, we propose a distributed multi-agent maze traversal algorithm for environments that can be represented by acyclic graphs. It uses a leader-switching mechanism where one agent, assuming a head role, employs any single-agent maze solver while the other agents each choose an agent to follow. The head role gets transferred to neighboring agents where necessary, ensuring it follows the same path as a single agent would. The multi-agent maze traversal algorithm is evaluated in simulations with groups of up to 300 agents, various maze sizes, and multiple single-agent maze solvers. It is compared against strategies that are naïve, or assume either global communication or full knowledge of the environment. The algorithm outperforms the naïve strategy in terms of makespan and sum-of-fuel. It is superior to the global-communication strategy in terms of makespan but is inferior to it in terms of sum-of-fuel. The findings suggest it is asymptotically equivalent to the full-knowledge strategy with respect to either metric. Moreover, real-world experiments with up to 20 Pi-puck robots confirm the feasibility of the approach.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Understanding Humans' Strategies in Maze Solving
Navigating through a visual maze relies on the strategic use of eye movements to select and identify the route. When navigating the maze, there are trade-offs between exploring to the environment and relying on memory. T…
Error UnderstandingThere is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes
Interpretability is an essential building block for trustworthiness in reinforcement learning systems. However, interpretability might come at the cost of deteriorated performance, leading many researchers to build compl…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Understanding and Controlling a Maze-Solving Policy Network
To understand the goals and goal representations of AI systems, we carefully study a pretrained reinforcement learning policy that solves mazes by navigating to a range of target squares. We find this network pursues mul…
MazeEval: A Benchmark for Testing Sequential Decision-Making in Language Models
As Large Language Models (LLMs) increasingly power autonomous agents in robotics and embodied AI, understanding their spatial reasoning capabilities becomes crucial for ensuring reliable real-world deployment. Despite ad…
Spatial ReasoningMazeNet: An Accurate, Fast, and Scalable Deep Learning Solution for Steiner Minimum Trees
The Obstacle Avoiding Rectilinear Steiner Minimum Tree (OARSMT) problem, which seeks the shortest interconnection of a given number of terminals in a rectilinear plane while avoiding obstacles, is a critical task in inte…