Search papers, labs, and topics across Lattice.
This paper introduces a distributed algorithm for multi-agent navigation in unknown maze-like environments, enabling agents to traverse cyclic graphs while minimizing collisions through local communication and leader-follower dynamics. The algorithm is proven to be complete and achieves a makespan that is asymptotically equivalent to optimal strategies, demonstrating efficiency in both time and space complexity. Simulations with up to 625 agents reveal significant improvements in fuel efficiency compared to a naive baseline, highlighting the effectiveness of coordinated exploration.
Agents can traverse complex maze environments more efficiently by leveraging local communication and leader-follower dynamics, achieving optimal performance with fewer resources.
Cave networks, pipe systems, and similar maze-like environments pose significant challenges for multi-agent navigation in unknown settings with limited communication. We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph. Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal while avoiding collisions. They coordinate via local communication using leader-follower relationships and leader switching. At any moment in time, exploration is performed by only one of the agents, which runs a single-agent maze solver. We prove that the algorithm is complete, that its makespan is asymptotically equivalent (in the number of agents) to that of an optimal full-knowledge strategy, and derive its time and space complexity. Simulations with up to $625$ agents show a decreasing average sum-of-fuels as the number of agents increases and demonstrate that the proposed approach outperforms a na\"ive baseline in which all agents independently execute the single-agent solver.
