RRT* variants for solving differential games
A probabilistically-complete and probabilistically-sound algorithm based on the RRT* is used to solve a pursuit-evasion game. The evader is trying to get to a goal region (shown in magenta) while avoiding collision with obstacles (shown in red) and avoiding capture by pursuers (initial locations shown by black dots). The pursuers also need to avoid collision with obstacles in this problem. Both evader and the pursuer(s) maintain an RRT*. The tree maintained by the evader is shown in the video. The trajectory of the evader (which is guaranteed to converge to a Stackelberg equilibrium of the game) is highlighted in red.
For more information see
http://ares.lids.mit.edu/rrtstar