A survey on Probabilistic Path Planner

A survey on Probabilistic Path Planner

Probabilistic Path Planner by Someshwar Marepalli Pratik Desai Ashutosh Sahu Gaurav jain Motion Planning Definition: Computation of a collision-free path for a movable object among obstacles. Applications: Building Maps

Assemble/De-assemble engines Tracking Targets Computational Biology Challenges in Motion Planning Obstacles Robot geometry Non Holonomic constraints Moving obstacles Uncertain sensing Inexact control Complete Planners

Definition: Planners that solve any solvable problem and return failure for each non solvable one. Real life environments demand Complete Planners. Solving even the basic path planning problem requires time exponential in the robots degrees of freedom. n robots of d degrees of freedom each, complexity

becomes exponential in nd. In the presence of moving obstacles, problem becomes exponential in their number. Uncertainties in the robots sensing and control, leads to an exponential dependency on the complexity of the obstacles. Weaker Complete Planners High complexity of Complete Planners make them impractical for most applications. Heuristic planners have been developed which can solve complicated problems but they fail for some simple ones.

Exists a substantial gap between the theoretical worst-case bounds of path planning algorithms and their practical complexity. Design planners that satisfy weaker forms of completeness like Probabilistic and Resolution completeness. Two successful planners which satisfy the former condition are Randomized Path Planner(RPP) and Probabilistic path Planner(PPP). Randomized Path Planner Potential field U is calculated giving positive and negative values to different configurations.

Attracting potential for the goal configuration and repulsive for the obstacles. By descending along U, we attempt to connect the start and the goal configuration. We hit upon a minima at the end of this process and if the minima encountered is the global minima, we have found a solution to the problem, else we perform Brownian motion to achieve it. Randomized Path Planner (contd) RPP proves to be very powerful in many cases but it has some drawbacks too,

Transition Probabilities Pijs are nontrivial in many cases Single shot approach of solving Simple problems consume a lot of time due to low transition probabilities It does not apply directly to non holonomic robots. Probabilistic Path Planner Very general Planner Builds probabilistic roadmaps by randomly selecting configurations

from the free configuration space and then interconnects some pairs by simple feasible paths. Its probabilistically complete and not restricted to any particular class of robots. Consists of two phases, Roadmap construction phase and Query Roadmap Construction Phase During this phase a data structure is incrementally constructed in a probabilistic way.

It is later used in the query phase for solving individual path planning problems Let Cf be the free configuration phase C R+ as the distance D C measure used Graph G = (V,E) Cf Cf2 is defined by the roadmap construction algorithm. Define

Roadmap Construction Phase The Roadmap construction algorithm: (1) V = ; E = ; (2) loop (3) c = a randomly chosen free configuration (4) V = V U {c} (5) Nc = a set of neighbours of c chosen from V (6)

For all n Nc, in order of increasing D(c,n) do Roadmap Construction Phase Local Planner: It constructs all paths feasible for the robot in the absence of obstacles. Features: It should construct paths in a time efficient manner Probability that local paths obstruct with obstacles should be low. It should guarantee probabilistic

completeness of PPP. Roadmap Construction Phase Neighbors and Edge adding Methods: Number of neighbors (Nc ) directly affects the time complexity Attempts to connect nodes that are already in cs connected component are useless. To avoid too many local planner failures, we only submit pairs of configurations whose relative distance is small (lessthan a threshold maxdist)

Roadmap Construction Phase Distance: Should be defined in such a way as to reflect the failure-chance well. Rough approximations of sweep volumes are generally preferred. Node Adding Heuristics: It is recommended to guide the node generation by heuristics that create higher node densities Query Phase

We try to connect the start configuration s and the goal configuration g to s` and g` respectively, subject to the fact that s` and g` belong to the same connected component of G and compute Ps`g` Concatenate Incase Pss` Ps`g` and Pg`g such a path does not exist

the query fails (preferably terminate instantaneously) Query Phase To find the nodes s` and g`, a C C function query_mapping V V is used. Defined as query mapping(a,b) =(a`,b`), such that a` and b` are connected, and D(a,a`)

+ D(b,b`) = MIN (x,y) W : D(a,x) + D(y, b) where W = {(x,y) V V | Query Phase Since no obstacle avoidance is incorporated in the Local Planner, it might turn out that the query might fails inspite of a well connected free C-space well. To avoid unnecessarily long

paths due to the probabilistic nature, one can smoothen the paths by picking a random path and replacing it by a shorter one. Thank you !!

Recently Viewed Presentations

  • Vocabulary Words - Vogel Biology

    Vocabulary Words - Vogel Biology

    Vocabulary Words. Please define the following vocabulary words. Cytoskeleton. Nucleus. Endoplasmic reticulum. Ribosome. Golgi apparatus. Vesicle. Mitochondria
  • Bacterial Cell Structure (continued)

    Bacterial Cell Structure (continued)

    Ways to think about peptidoglycan * Bacterial Cell Structure (continued) You are here. Gram negative cell wall Outer membrane Lipid bilayer membrane: Asymmetric Inner and outer leaflets Inner leaflet made of phospholipids; outer leaflet is made of lipopolysaccharide (LPS) LPS...
  • Lesson 2.4: Stop the spread PPT 2.4 - Cornell University

    Lesson 2.4: Stop the spread PPT 2.4 - Cornell University

    What was your reaction to how much Glo Germâ„¢ remained on your or someone else's hands after washing? What areas of the hands retained the most Glo Germâ„¢ and were the most difficult to wash? Frequent, proper hand washing is...
  • akhull.weebly.com


    Standard Kesho is generally used in Wagato Kabuki, and also for the Onnigato. A white base is used for all roles. High status characters have pure white make up, lower class characters add a brownish tinge to show they work...
  • Completing a leadership observation - Weebly

    Completing a leadership observation - Weebly

    Completing a leadership observation . Marzano school leadership 2014-2015. Leadership observation domains ... Step 6- Upload documents (maximum of 2)for each element . Use the "Marzano Leadership Model with Marzano and OKCPS Evidences" to find specific options for you to...
  • Opiates & Opiate Blockers - Chemeketa Community College

    Opiates & Opiate Blockers - Chemeketa Community College

    Pharmacology - Pot-pourri Peggy Andrews, Instructor Chemeketa CC Analgesics Opiates & Opiate Blockers We'll talk about Buprenex Stadol Vicodin Demerol Morphine sulfate Fentanyl Nubain Trexan Narcan Buprenex buprenorphine Class Opioid analgesic (agonist - antagonist) Schedule V Indications Management of moderate...
  • IES Webinar: Overview

    IES Webinar: Overview

    Purpose of Early Career Program. Develop and maintain a strong cadre of independent researchers addressing the needs of infants, toddlers, children, and youth with disabilities, and their families and teachers. Provide support for an . integrated research and career development...
  • What: Explore Approaches to Learning in the DP

    What: Explore Approaches to Learning in the DP

    Explore MYP and DP specific ATL materials on ibo.org. ... (OCC) If you don't have your OCC log in, use mine. School Code: 5652. Username: michaelc. ... Find an activity or practice on your OCC site and then explain why...