Skip to content

Home

Jump to bottom
Umang Rastogi edited this page Dec 28, 2020 · 2 revisions

Overview

This project is an implementation of the 3 algorithms described in the paper: dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning in a 2D environment using Python as the programming language. The algorithms are:

  • Discrete RRT (dRRT)
  • Asymptotically Optimal Discrete RRT (ao-dRRT)
  • dRRT*

The implementation of these algorithms can be found here.

ao-dRRT and dRRT* have shown to be scalable with low variance in first solution time for multi-robot planning. Therefore, they form an essential baseline for our research project on Multi-Robot Motion Planning using MPNet, where MPNet stands for Motion Planning Networks. They will be used to draw a comparison with the multi-robot MPNet algorithm we are working on.

Project members

Modifications

  • We implement the algorithms on a 2D polygonal environment for 2 robots similar to the paper. However, we have used our own environment of size 100x100 to put the algorithms to a test for impending collisions.
  • Our map includes a high-probability collision region (HPCR) in the center for the same. (Refer figure 1)
  • The robots start from opposite sides of the high-probability collision region with their target location on the diagonally opposite corner of the map. The start and target positions ensure that the robots must cross the high-probability collision region and thus face impending collision.
  • Figure 1 below indicates one of the starting of the robots.


Figure 1 - Map indicating start positions of the robots

  • Look at figure 2 for the initial roadmap provided to the algorithms. The initial roadmap is generated using PRM as described in the paper.


Figure 2 - Initial roadmap provided to each of the algorithms

Results

  • First, let us see the path computed by each of the algorithms in figure 3. We can see that the paths get better as we move from the dRRT solution to ao-dRRT solution. The dRRT* solution is the most optimal among the 3 algorithms.
dRRT ao-dRRT dRRT*


Figure 3 - Path computed by all the algorithms

  • We have tried to reproduce the first solution time graph mentioned in the paper. Figure 5 shows the first time solution plot from the paper.
  • Figure 4 shows the time taken by dRRT, ao-dRRT, and dRRT*, respectively, to find the first solution for the same start and end configuration.
  • We have calculated the first solution time for nodes=9 and nodes=42. For the nodes=42 case, we have 2 sub-cases: one in which the robots do not have to pass through the HPCR and a hard case where the robots have to crossover the HPCR. Note that the sub-cases have been referred to as 42 simple and 42 difficult in figure 3.


Figure 4 - First solution time for various cases using our implementation

  • Comparing figures 4 and 5, we can say that our implementation is slower than the one through which paper results have been derived. This might be for multiple reasons: difference in processing power or due to the overhead of Python as implementations are usually faster when done in languages, such as C++ and Java. The system used by the authors had 128 GB of RAM while our implementation ran on a system with only 16 GB of RAM.
  • However, we can notice the scalability of dRRT* that outputs results in a matter of few milliseconds even when the number of nodes is increased in the last 2 cases.


Figure 5 - Original 1st solution time results from the paper


Figure 6 - Query times for each of the cases along with all the algorithms

  • The table in figure 6 (above) shows query-time, path length, and the number of iterations it took in each case for dRRT, ao-dRRT, and dRRT* respectively.
  • Note that we have not tried to reproduce the solution cost versus iterations graph as it did not make sense to run 100,000 iterations for a difference less than a unit as compared to the first solution cost.

Challenges

  • The main challenge was to understand the algorithm. Some subroutines within the algorithms such as connect_to_target, trace_path, and the steering function, L(.), have not been mentioned with great clarity that makes them difficult to implement. Authors had to be contacted to gain clarity on the methods.

*Note that the various images included here are either self-created or sourced from the dRRT* paper.

Clone this wiki locally