ICRA 2011 Paper Abstract


Paper ThA203.4

Sarid, Shahar (Ben-Gurion University of the Negev), Shapiro, Amir (Ben Gurion University of the Negev), Rimon, Elon (Technion - Israel Institute of Technology), Edan, Yael (Ben-Gurion University of the Negev)

Classifying the Heterogeneous Multi-Robot Online Search Problem into Quadratic Time Competitive Complexity Class

Scheduled for presentation during the Regular Sessions "Path Planning for Multiple Robots II" (ThA203), Thursday, May 12, 2011, 10:50−11:05, Room 3D

2011 IEEE International Conference on Robotics and Automation, May 9-13, 2011, Shanghai International Conference Center, Shanghai, China

This information is tentative and subject to change. Compiled on August 19, 2019

Keywords Path Planning for Multiple Mobile Robots or Agents, Motion and Path Planning, Distributed Robot Systems


We explore the problem where a group of robots with different velocities search for a target in an unbounded unknown environment. The target position is unknown, hence, an online search algorithm is developed. The H-MRSTM algorithm (Heterogeneous Multi-Robot Search Time Multiplication), launches a group of n robots from a common starting location to search for the target. The robots are assigned to search inside a series of concentric discs with increasing radii. Each robot is assigned to search inside a disc and when completing the search inside this disc without finding the target, the robot is assigned to search in the next unoccupied disc. We prove that every algorithm that solves this search problem must have at least a quadratic time competitive complexity and prove that the H-MRSTM algorithm's complexity is also quadratic. Hence, we obtain both an upper and lower bound on the time competitive complexity of the search problem. Consequently, H-MRSTM is proved to be optimal. Simulations in various environments show that the average case performance of H-MRSTM is superior to that of homogeneous multi-robot and single robot algorithms. In depth simulation analyses evaluated the effect of several other parameters such as the initial disc search time, the distribution of the velocities, the number of robots and the position of the target.



Technical Content © IEEE Robotics & Automation Society

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2019 PaperCept, Inc.
Page generated 2019-08-19  19:59:22 PST  Terms of use