Overview of Probabilistic Roadmaps for Path Planning

Exploring the concept of Probabilistic Roadmaps (PRMs) for efficient path planning in dynamic environments. The approach involves constructing a roadmap through uniform sampling, allowing for multiple queries in the same environment. Key aspects covered include completeness, challenges with classic approaches, assumptions, and the overall process flow from precomputation to query processing.

• Path Planning
• Probabilistic Roadmaps
• PRM Approaches
• Roadmap Construction
• Uniform Sampling

hast_5 Follow

Uploaded on Sep 24, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. CS686: Probabilistic Roadmaps Sung-Eui Yoon ( ) Course URL: http://sgvr.kaist.ac.kr/~sungeui/MPA

2. Class Objectives Understand probabilistic roadmap (PRM) approaches Multi-query PRMs Last time: Proximity queries: collision detection and distance computation 2

3. Difficulty with Classic Approaches Running time increases exponentially with the dimension of the configuration space For a d-dimension grid with 10 grid points on each dimension, how many grid cells are there? 10d Several variants of the path planning problem have been proven to be PSPACE- hard 3

4. Completeness Complete algorithm A complete algorithm finds a path if one exists and reports no otherwise Example: Canny s roadmap method Heuristic algorithm Unreliable Example: potential field Slow Probabilistic completeness Intuition: If there is a solution path, the algorithm will find it with high probability 4

5. Probabilistic Roadmap (PRM): multiple queries local path free space milestone [Kavraki, Svetska, Latombe,Overmars, 96] 5

6. Assumptions Static obstacles Many queries to be processed in the same environment Examples Navigation in static virtual environments Robot manipulator arm in a workcell 6

7. Overview Precomputation: roadmap construction Uniform sampling Resampling (expansion) Query processing 7

8. Uniform sampling Input: geometry of the moving object & obstacles Output: roadmap G = (V, E) 1: V and E . 2: repeat 3: q a configuration sampled uniformly at random from C. 4: ifCLEAR(q)then 5: Add q to V. 6: Nq a set of nodes in V that are close to q. 6: for each q Nq, in order of increasing d(q,q ) 7: ifLINK(q ,q)then 8: Add an edge between q and q to E. The graph G is called a probabilistic roadmap The nodes in G are called milestones 8

9. Difficulty Many small connected components 9

10. Resampling (expansion) failed #. LINK Failure rate = ( ) r q LINK #. ( ) r q = ( ) w q Normalized weight ( ) r p p Resampling probability q = Pr ( ) ( ) w q 10

11. Resampling (expansion) 11

12. Query processing Connect qinitand qgoal to the roadmap Start at qinitand qgoal, perform a random walk, and try to connect with one of the milestones nearby Try multiple times 12

13. Error If a path is returned, the answer is always correct If no path is found, the answer may or may not be correct. We hope it is correct with high probability. Refer to Theoretical Analysis of my draft L: path lengths, N: # of samples, D is dimension R: the clearance between the robot and obstacles 13

14. Smoothing the path 14

15. Smoothing the path 15

16. Sampling Strategies Visibility-based Probabilistic roadmaps for Motion planning The Gaussian Sampling Strategy for PRM s Sample near the boundaries of the C-space obstacles with higher probability 16

17. Visibility-based PRM Computes a very compact roadmap Classical PRM Visibility roadmap 17

18. Visibility Domain Visibility domain of a free configuration q: The grey region q 18

19. Guard Nodes The C-space fully captured by guard nodes 19

20. Guard Nodes The C-space fully captured by guard nodes. 20

21. Guard Nodes The C-space fully captured by guard nodes. 21

22. Connection Nodes The C-space being captured by guards and connection nodes. 22

23. Connection Nodes The C-space being captured by guards and connection nodes. 23

24. Connection Nodes The C-space fully captured by guards and connection nodes. We do not need any other additional node in the roadmap 24

25. Remarks Maintains a very compact roadmap, resulting in faster query time But: There is a tradeoff with high cost of processing each new milestone How many iterations needed to capture the full connectivity? The problem of capturing the narrow passage effectively is still the same as in the basic PRM. 25

26. Summary What probability distribution should be used for sampling milestones? How should milestones be connected? A path generated by a randomized algorithm is usually jerky. How can a path be smoothed? Single-query PRMs were proposed, but RRT techniques are more widely used 26

27. Class Objectives were: Understand probabilistic roadmap (PRM) approaches Multi-query PRMs 27

28. Next Time.. RRT techniques and their recent advancements 28

29. Homework for Every Class Submit summaries of 2 ICRA/IROS/RSS/CoRL/TRO/IJRR papers Go over the next lecture slides Come up with three question before the mid- term exam 29

30. Figs 30

31. Probabilistic Roadmap (PRM): multiple queries local path free space milestone 31

32. Difficulty 32

33. Smoothing the path 33

34. b) A new guard node a) Guard node and its visibility domain c) Connection nodes 34

35. ?? ??+? ?/? ? 35