NDLI: An Application of Pebble Motion on Graphs to Abstract Multi-robot Path Planning

Content Provider	IEEE Xplore Digital Library
Author	Surynek, P.
Copyright Year	2009
Abstract	An abstraction of a problem of rearranging group of mobile robots is addressed in this paper (the problem of multi-robot path planning). The robots are moving in an environment in which they must avoid obstacles and each other. An abstraction where the environment is modeled as an undirected graph is adopted throughout this work. A case when the graph modeling the environment is bi-connected is particularly studied. This paper puts into a relation the well known problems of moving pebbles on graphs (sliding box puzzles) with problems of multi-robot path planning. Theoretical results gained for problems of pebble motion on graphs are utilized for the development of algorithms for multi-robot path planning. As the opti-mization variant of both problems (a shortest solution is required) is known to be computationally hard (NP-hard), we concentrate on construction of sub-optimal solving procedures. However, the quality of solution is still an objective. Therefore a process of composition of a sub-optimal solution of the problem (a plan) of the pre-calculated optimal plans for the sub-problems (macros) is suggested. The plan composition using macros was inte-grated into two existing sub-optimal solving algorithms. In both cases, substantial improvements of the quality of resulting plans were achieved in comparison to the origi-nal algorithms. The no less important result is that one of the existing algorithms was generalized by integrating macros for larger class of problems of multi-robot path planning.
Starting Page	151
Ending Page	158
File Size	1050588
Page Count	8
File Format	PDF
ISBN	9781424456192
ISSN	10823409
DOI	10.1109/ICTAI.2009.62
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-11-02
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Path planning Robot kinematics Orbital robotics Mobile robots Robotics and automation Artificial intelligence Contracts Application software Mathematics Physics pattern database planning multi-robot graph puzzle pebble motion
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A hierarchical decoupled approach for multi robot motion planning on trees

Web Accessibility Issues for the Distributed and Interworked Enterprise Portals

Neural algorithms of path planning for mobile robots in transport systems

Multi-Robot Motion Planning by Incremental Coordination

Multi-agent path planning with multiple tasks and distance constraints

A decentralized local constraint path planner for multiple mobile robots

Closed loop motion plans for mobile robots

Motion planning for a non-holonomic mobile robot on 3-dimensional terrains

Coordinated motion planning for multiple car-like robots using probabilistic roadmaps

An Application of Pebble Motion on Graphs to Abstract Multi-robot Path Planning

Similar Documents

A hierarchical decoupled approach for multi robot motion planning on trees

Web Accessibility Issues for the Distributed and Interworked Enterprise Portals

Neural algorithms of path planning for mobile robots in transport systems

Multi-Robot Motion Planning by Incremental Coordination

Multi-agent path planning with multiple tasks and distance constraints

A decentralized local constraint path planner for multiple mobile robots

Closed loop motion plans for mobile robots

Motion planning for a non-holonomic mobile robot on 3-dimensional terrains

Coordinated motion planning for multiple car-like robots using probabilistic roadmaps

An Application of Pebble Motion on Graphs to Abstract Multi-robot Path Planning