2022/10/08 by Jared Coleman, Evangelos Kranakis, Coleman, Jared +5
Computer Science · #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Robotic Path Planning Algorithms #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2210.04080
openalex publication_date 2022/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two cooperating, autonomous mobile robots with arbitrary nonzero max speeds are placed at arbitrary initial positions in the plane. A remotely detonated bomb is discovered at some source location and must be moved to a safe distance away from its initial location as quickly as possible. In the Bomb Squad problem, the robots cooperate by communicating face-to-face in order to pick up the bomb from the source and carry it away to the boundary of a disk centered at the source in the shortest possible time. The goal is to specify trajectories which define the robots' paths from start to finish and their meeting points which enable face-to-face collaboration by exchanging information and passing the bomb from robot to robot. We design algorithms reflecting the robots' knowledge about orientation and each other's speed and location. In the offline case, we design an optimal algorithm. For the limited knowledge cases, we provide online algorithms which consider robots' level of agreement on orientation as per OneAxis and NoAxis models, and knowledge of the boundary as per Visible, Discoverable, and Invisible. In all cases, we provide upper and lower bounds for the competitive ratios of the online problems.