100 %
0 %
Information about paper2

Published on January 3, 2008

Author: Peppar


Using a PRM Planner to Compare Centralized and Decoupled Planning for Multi-Robot Systems:  Using a PRM Planner to Compare Centralized and Decoupled Planning for Multi-Robot Systems Gildardo Sanchez Jean-Claude Latombe Paper Presentation By Mohammad Irfan Rafiq Reusing slides from Chris Enedah(2003) PRM Path Planner: Sampling Strategy:  PRM Path Planner: Sampling Strategy SBL Planner Single-query Bi-directional Lazy collision-checking Multi-Robot Planning Examples:  Multi-Robot Planning Examples Multi-Robot Planning:  Multi-Robot Planning An initial and a goal configuration are given as input for each robot Result is a coordinated path between the two configurations A coordinated path is one that indicates the configuration of every robot at each instant Collisions must be avoided between each pair of robot and obstacles, and between each pair of robots Centralized Planning:  Centralized Planning Paths for all robots are planned simultaneously by searching the c-space of the multi-arm robot Collisions between robots are self-collisions of the multi-arm robot For spot-welding example, 6 robots each with 6 dofs, so C will have 36-D Centralized Planning:  Centralized Planning Advantages Complete – guaranteed to find a solution if one exists (if the underlying planner is complete) Disadvantages Potentially expensive – typically requires searching high-dimensional spaces Requires knowledge of goals and states of all robots Decoupled Planning:  Decoupled Planning First Phase - a collision-free path ti is generated for each robot considering only obstacles (ignoring other robots) in its space Decoupled Planning:  Decoupled Planning Second Phase (Velocity Tuning) – coordination of the robots’ velocities along their pre-generated paths to prevent collisions between robots. Two coordination methods discussed Pairwise Coordination Global Coordination Each robot is restricted to motion in its pre-generated path although it may stop, retreat or change velocity to allow coordination with other robots Decoupled Planning with Pairwise Coordination:  Decoupled Planning with Pairwise Coordination The paths t1 and t2 of the first two robots are coordinated in their 2-dimensional coordination space Results in a collision-free coordinated patht1,2 Done by using planning a path between (0,0) and (1,1) Decoupled Planning with Pairwise Coordination:  Decoupled Planning with Pairwise Coordination The process is repeated for paths t1,2 and t3 resulting in a coordinated path t1,2,3 Eventually a collision-free coordinate path t1,2,…,m is generated that defines a valid coordination of all m robots Decoupled Planning with Global Coordination:  Decoupled Planning with Global Coordination The paths of all m robots are coordinated in an m-dimensional coordination space Results in a collision-free path t1,2,….m Done by planning a path from (0,0,0,…) to (1,1,1,…) Decoupled Planning:  Decoupled Planning Advantages Less expensive than centralized planning because lower dimensional spaces are searched Disadvantages Incomplete : Failures usually occur in the second phase as it might not be possible to coordinate the paths generated in the first phase without collision between robots Decoupled Planning Failure Example:  Decoupled Planning Failure Example Initial and goal configurations Decoupled Planning Failure Example:  Decoupled Planning Failure Example Likely path generation in 1st phase Decoupled Planning Failure Example:  Decoupled Planning Failure Example Path coordination fails in second phase Implemented Planners:  Implemented Planners C-SBL – Centralized Planning DG-SBL – Decoupled Planning with Global Coordination DP-SBL – Decoupled Planning with Pairwise Coordination Experiments conducted with groups of 2, 4 and 6 robots on 3 separate sets of initial/goal configurations Problem I – Initial and goal configurations:  Problem I – Initial and goal configurations Problem II – Initial and goal configurations:  Problem II – Initial and goal configurations Problem III – Initial and goal configurations:  Problem III – Initial and goal configurations Experimental Results:  Experimental Results T = average running time (seconds) DG-SBL and DP-SBL - 20 runs per experiment C-SBL – 100 runs per experiment F = number of failures Maximum of 50,000 milestones allowed per call to SBL Experimental Results:  Experimental Results Centralized planning had no failures At least one failure suffered in each experiment with decoupled planning Failure rate increased as problems became more complex Experimental Results:  Experimental Results pairwise coordination more unreliable than global coordination Failure always occurred in the 2nd stage during path coordination, a result of wrong path choices made in the 1st stage Experimental Results:  Experimental Results Similar running times for both planners in most experiments However, centralized planning required a lot more time than decoupled planning in 3rd problem with 6 robots Conclusions:  Conclusions Reliability – Decoupled planning can be quite unreliable particularly in tight robot coordination. Centralized planning appears to have perfect reliability. Planning Time – Using SBL, there is not a huge difference between the two methods Conclusions Contd.:  Conclusions Contd. Results invalidate the assumptions that loss of incompleteness with decoupled planning is fairly insignificant and can be ignored in practice. SBL makes usage of centralized planning for multi-robot systems practical. But centralized planning still requires knowledge of all robot states, which may be impossible in some settings.

Add a comment

Related presentations

Related pages


Welcome to the Paper2 online store! Hession Bag - Pack of 2. $11.90. Chalkboard Stakes - Pack of 5. $20.00. delfonics pen - large. $12.95. terms & conditions;
Read more

paper2 - Scribd - Read books, audiobooks, and more

paper2. by Meor Zulkernaen B Zabidin. 0 views. Embed. Download. Description. Soalan Matematik Kertas 2. Soalan Matematik Kertas 2. Categories: Types ...
Read more

Jeemains2014key Paper2

Browse and Read Jeemains2014key Paper2 Jeemains2014key Paper2 Title Type jeemains2014key paper2 PDF memorandum sg paper2 set a PDF physics hl paper2 tz1 PDF
Read more

Paper2 - Search results

Search. search. Advanced search. 222 results found Displaying: 1 - 30 results Search Results. 1; 2; 3; 4; 5; 6; 7; 8 "From the Library of" Stamp. Sold Out
Read more

Paper2 Agriculture

Browse and Read Paper2 Agriculture. Title Type chemistry theory paper2 2014 15 april answer PDF november 2013 physics paper2 memo grade 12 PDF physical ...
Read more

English Question Paper2

Get Instant Access to PDF Read Books English Question Paper2 at our eBook Document Library 1/12 English Question Paper2 English Question Paper2 PDF
Read more

Berabecka Boandl-Bräu

Berabecka Boandl-Bräu.
Read more


Abstract The silicalite-water potential function has been developed using quantum chemical calculations at the Hatree-Fock level using the extended 6-31G ...
Read more

Geography Paper2 Grade11

Download and Read Geography Paper2 Grade11 Geography Paper2 Grade11 Title Type geography paper2 grade11 PDF geography paper2 grade11 exemplar 2013 PDF
Read more - Datei nicht gefunden

Leider konnte Ihre hochgeladene Datei nicht gefunden werden. Laden Sie die Datei neu hoch.
Read more