Informed RRT*

Authors: Avery Dibble, Andrew Wong

EGP-410 “Game AI”

12/10/2018

Research Project Blog Post: Informed RRT* 

Download the demo here! (Requires Unity Editor)

For our final project, we decided to implement a Rapidly-exploring Random Tree (RRT) algorithm, which is a pathfinding algorithm used in open world environments with no discrete nodes. As the name suggests, the algorithm takes a starting position and expands outward in a random direction for a random distance. The end of each of these expansions becomes a self-created node, which can further be expanded from in the same faction.

The algorithm will keep expanding from nodes until it reaches the target location, at which point a solution has been found.

Several variations and extensions of this pathfinding algorithm exist, most of them using cost functions and heuristics based on distance from the node’s location to the target location, or other features used to either steer the algorithm towards the target faster or to optimize the path found.

Informed RRT*, which is the variation that we chose to implement, uses both a distance-based cost function as well as an iterative optimization function to improve the efficiency of the path once a solution has been found. The way the informed RRT* iteratively improves upon a found path is by creating a “prolate hyperspheroid” that encapsulates the start node, path, and goal. Any further expansions can only fall within this area.

The algorithm then performs an optimization loop. During the optimization loop, a n size batch of expansions are made from the path, and if any of them end in solutions, they are compared to the existing solutions. If a more efficient path solution has been derived from the existing best solution, then that becomes the new best solution and the “prolate hyperspheroid” shrinks to only encapsulate that solution.

This optimization process continues until either the specified number of optimization loops has been reached – there is a setting in our tech demo to dynamically change how many optimization loops are run – or until convergence is reached and a better path cannot possibly be found.

This type of technique could be put to use in open world games, first person shooters or any game where an AI agent would need to traverse an organically-shaped environment. It could even work in 2D top-down games that involve navigating an area filled with obstacles, which would be a similar implementation to the tech demo. This algorithm would find it’s optimal use in a low clutter, organically shaped environment where a grid might be too constrained than is desirable for pathfinding.

As for platforms, informed RRT* would probably be a good fit for game engines such as Unity or Unreal as the random expansion part of the algorithm is simplified greatly by both Unity’s raycasting and Unreal’s NavMesh functionalities. As implemented, the algorithm is expensive and kludged together, but could be easily improved through better use of data structures and the use of pointers, which we avoided due C#’s limited support for them. 

 

References

 

https://arxiv.org/pdf/1404.2334.pdf: This contributed to our understanding of Informed RRT* by going into an in-depth description of the process of the algorithm and what distinguishes it from normal RRT*. This allowed us to conceptualize and implement the base RRT algorithm and understand how to perform the informed optimization after finding the solution.

 

Informed RRT* @ UTIAS (IROS 2014): This source was useful because alongside the brief overview of the algorithm, it also showed a visualization of it in action. this not only helped us understand how the algorithm worked, but also gave us an example to model our own visualization after in our tech demo.

 

https://arxiv.org/pdf/1405.5848.pdf: This article was important because it further explained the process the informed RRT* uses to perform its optimization loop.. This also allowed us to conceptualize the code so we could implement it in our own project.