This discrete-search algorithm, published
by
Daniel, Nash, Koenig and Felner in 2010, is an extension of A*. By maintaining angle ranges
(shown in
green)
of unobstructed space, it can avoid some collision checks. Implemented in Python, over a number of
spare
weekends during my time at Uber ATG; here is the code.
In some graph-based motion-planning problems, the performance bottleneck is edge evaluations -- for instance, if edges represent configuration-space motions of a robot arm and we must use forward kinematics to check them for collisions. This competition, inspired by Dellin and Srinivasa's 2016 LazySP paper, provides a way to test and compare algorithms in an environment with strictly limited edge evaluations.
This webpage (click for animation) shows the path of the Voyager 2 space probe as it uses gravity assists to visit Jupiter, Saturn, Uranus, and Neptune. I made it during the vacation between two terms of college in order to learn web development.