paper2

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.