Collision-free robot movement methods improve distance efficiency on grids and graphs

Collision-free Movement on Grids and Beyond

Multiagent SystemsData Structures and Algorithms

Summary

This work looks at how to move multiple robots around on networks like grids without them crashing into each other, while trying to keep their total travel distance as short as possible. The authors focus on situations where robots need to end up connected in a group rather than assigned specific spots. They study how complex it is to find optimal movements under these rules on different kinds of networks like grid layouts, planar maps, and overlapping areas. Their analysis extends prior work that either ignored collisions or assigned fixed targets to each robot. This helps better understand the limits and possibilities of coordinating robot movements safely and efficiently.

What this means in practice

  • For warehouse automation teams: Coordinate multiple robots moving goods to connected target zones on grid-based layouts without collisions and with minimal total movement.
  • For wireless sensor network designers: Design algorithms that reposition sensors to maintain connected formations efficiently without node collisions in planar and unit disk graphs.

A theory result. No direct application yet.

Authors

Hendrik Molter, Meirav Zehavi

Abstract

We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property while minimizing the total travel distance. This framework extends two classical models: (a) minimizing movement [Demaine et al., TALG '09, '14], which does not enforce collision avoidance, and (b) coordinated motion planning or multi-agent path finding [Eiben et al., SoCG '23, Deligkas et al., ICALP '24, among many others], where each robot is assigned an explicit target position. We focus on the setting where the target formation of the robots should be connected. We analyze the parameterized complexity of the problem with respect to the number of (main) robots and the total travel length on grid graphs and two natural generalizations thereof: planar graphs and unit disk graphs.
View PDFOpen arXiv