Group of robots motion planning

From BGU Robotics Lab
Jump to: navigation, search

Search for a target or for a path to the target with group of autonomous robots: In this work we explored two on-line multi-robot motion planning problems where a group of robots must reach a target in an unknown unbounded planar environment whose geometry is acquired by the robots' sensors during task execution. In the first problem, the target position is unknown and should be found by the robots, while in the second problem the target position is known and a collision-free path to it should be found. Examples for possible applications are search and rescue missions, cleaning supermarkets, detecting contaminated substances in factories or in the open field, planetary exploration and sample acquisition. This work describes two new on-line motion planning algorithms which solve the problems. The first is called MRSAM, short for Multi-Robot Search Area Multiplication, and the second is called MRBUG, short for Multi-Robot BUG algorithm. We prove that both algorithms are optimal in the sense of having shortest search time in worst case scenario. We further extended the algorithms to deal with heterogeneous velocity robots. We developed HMRSTM, short for Heterogeneous Multi-Robot Search Time Multiplication, and HMRBUG, short for Heterogeneous Multi-Robot BUG algorithms and proved their optimality. The algorithms' average case performance had been simulated in office-like environments, and tested in experiments.


Shahar Sarid, Amir Shapiro, “Classifying the Multi Robot Path Finding Problem into a Quadratic Competitive Complexity Class”, Springer-Verlag Dordrecht publishers, Annals of Mathematics and Artificial Intelligence, Volume 52(2-4):169–203, April 2008. (PDF)

Shahar Sarid, Amir Shapiro, “H-MRSTM: A Competitive Search Algorithm for Heterogeneous Group of Robots”, International Journal of Factory Automation, Robotics and Soft Computing, Issue 3: 51-58, July 2009. (PDF)

Shahar Sarid, Amir Shapiro, Elon Rimon, Yael Edan, “Classifying The Heterogeneous Multi Robot Online Search Problem Into Quadratic Time Competitive Complexity Class”, IEEE International Conference on Robotics & Automation (ICRA), May 2011, Shanghai, China. (acceptance rate 49%) (PDF)

Shahar Sarid, Amir Shapiro, “A Time Competitive Heterogeneous Multi Robot Path Finding Algorithm”, IEEE/RSJ International Conference on Intelligent Robots and Systems, (IROS 2010), October 18-22, 2010, Taipei, Taiwan.(acceptance rate 49.6%) (PDF)

S. Sarid, A. Shapiro, Y. Gabriely, "MRBUG: A Competitive Multi Robot Path Finding Algorithm", IEEE International Conference on Robotics & Automation, pages: 877-882, April 2007, Rome Italy. (acceptance rate 43.7%)

S. Sarid, A. Shapiro, Y. Gabriely, "MRSAM: A Quadratically Competitive Multi-Robot Online Navigation Algorithm", IEEE International Conference on Robotics & Automation, pages: 2699-2704, May 2006, Orlando, FL, USA. (acceptance rate 38.7%)

Shahar Sarid, Amir Shapiro, Yael Edan , “Algorithm for finding a path to a target with heterogeneous group of robots”, 3rd Israeli Conference on Robotics, Herzlia, Israel , 10-11 November, 2010.

S. Sarid, A. Shapiro, Y. Edan “H-MRSTM: Hetrogenous Multi Robot Time Competitive Motion Planning Algorithm, Performance Analysis and Simulations”, AUVSI-IEEE joint conference, Beer Sheva, Israel, October 6, 2010

Shahar Sarid, Amir Shapiro, Yael Edan, “Algorithm and Simulations for Finding a Target With Robots With Different Velocities”, The 31st Israeli Conference on Mechanical Engineering, Tel-Aviv, Israel, 2-3 June 2010.

S. Sarid, A. Shapiro, and Y. Gabriely, "Online Motion Planning Algorithm for a Group of Robots Obtaining a Common Goal" Israeli Conference of Robotics (ICR), June 2006, Tel Aviv, Israel.

Shahar Sarid, Multiple Robots Motion Planning Obtaining a Common Goal, Department of Mechanical Engineering, Ben Gurion University of the Negev, M.Sc. Thesis, 2007. Advisor: Dr. Amir Shapiro

Shahar Sarid, Heterogeneous Multi Robot Search Algorithms, Department of Mechanical Engineering, Ben Gurion University of the Negev, Ph.D. Thesis, 2011. (PDF) Advisors: Dr. Amir Shapiro and Prof. Yael Edan

Video Files

HMRSTM algorithm simulation

HMRSTM algorithm experiment

HMRBUG algorithm simulation

HMRBUG algorithm experiment