RU-RRT*

ENPM661 - Project Presentation

Presentation by Ruthwik & Zahir

Group 2

RRT*

• Tree emerging from start node
• RRT* Graph is dependent on Start Node
• Concept of ‘FLOW’
• Flow Direction

• Single query Path planning Algorithm

• Store current graph
• Store graph trees - which are eligible

RU-RRT*

PIPELINE

01

02

Perform RRT*

Check if we can use any trees form the previous graph

03

Join the stored query graphs to current graph and update parents, costs

04

For every query :

After Completion

Literature Review

RU-RRT*

Pseudo Code

Pseudo Code

R

R

T*

RU-RRT* [2]

RU-RRT* [3]

RU RRT* Implementation

Large Map - Graphs generated

Results and Inferences

Comparison:

RRT*

• Number of nodes in RRT* increases exponentially

​

Number of Nodes explored at the given time

Ru-RRT*

Sudden increase in number of nodes in Ru-RRT* due to large tree dump

Results and Inferences

In 1st query

​

• Both RRT* and Ru-RRT* are random
• Goal reach time and cost are random

​

In 2nd query

​

• RRT* is random
• Ru-RRT* uses tree from previous flow and adds to the current tree
• Goal reach time is less for Ru-RRT* and is optimal

​

Goal Cost Vs Time

Results and Inferences

Multiple Queries shown here

Goal Reach Time is less for RU-RRT* as compared to RRT*

Goal Reach Time

Cost Values

Goal Cost is less for RU-RRT* as compared to RRT*

• For 1st Query RU-RRT* performs same as RRT* [completely random]
• For next Queries the Goal reach time is less than RRT*
• For next Queries the Cost Values is less or similar to RRT*

Conclusion

• RU-RRT* stores the flow and trees of the RRT* in the form of FLOW Matrix externally

​

• For a new Query, RU-RRT* monitors the FLOW of the tree in real time, and checks if this FLOW already exists

​

• If exists, it imports the entire tree into the current Query and adds to its local graph.

​

• It continues sampling with the new graph.

​

​

Why Ru-RRT*

​

• ReUsable-RRT* Performs better than RRT* in following aspects
• No of nodes explored
• Time taken to reach Goal Node
• SAME cost or better

​

​

• ReUsable RRT* makes use of prior information - Trees created by prior queries

​

• RRT* - Creates incredibly straight paths
• Quickest path to location.......... BUT, Computationally expensive

​

• RURRT - Straight, Quick, Easy Computation

Maintaining Costs, Child Data

Trees Connecting

Randomness

HEAVY TREE DUMP

• Updating trees cost during rewiring
• Deletion of child nodes, updating parent nodes

• Updating costs throughout the new tree
• Check for existing nodes, not to insert new nodes

• Larger trees
• Biased direction - from start node
• -- Need to improve on the best tree [sorting] selection criteria

• Generating Results
• In each run, we are getting different results, -> affecting inference
• So, we had to do multiple runs and take average

Wrong Direction Exploration weight

Problems and Future work

• No of nodes on the non-goal side of the graph increases
• This in turn increases unwanted computation

Thank you

Group Number

2

Connecting

Trees

https://drive.google.com/file/d/1orQiNgzIabqcfrwn7u-_5mpPbsyq4fJQ/view?usp=sharing