Tech Briefs

Surface Navigation Using Optimized Waypoints and Particle Swarm Optimization

This technique could be used in search and rescue, tracking, military scouting, navigation, and as a field resource support tool.

The design priority for manned space exploration missions is almost always placed on human safety. Proposed manned surface exploration tasks (lunar, asteroid sample returns, Mars) have the possibility of astronauts traveling several kilometers away from a home base. Deviations from pre-planned paths are expected while exploring. In a time-critical emergency situation, there is a need to develop an optimal home base return path. The return path may or may not be similar to the outbound path, and what defines optimal may change with, and even within, each mission.

A novel path planning algorithm and prototype program was developed using biologically inspired particle swarm optimization (PSO) that generates an optimal path of traversal while avoiding obstacles. Applications include emergency path planning on lunar, Martian, and/or asteroid surfaces, generating multiple scenarios for outbound missions, Earth-based search and rescue, as well as human manual traversal and/or path integration into robotic control systems. The strategy allows for a changing environment, and can be re-tasked at will and run in real-time situations.

Given a random extraterrestrial planetary or small body surface position, the goal was to find the fastest (or shortest) path to an arbitrary position such as a safe zone or geographic objective, subject to possibly varying constraints. The problem requires a workable solution 100% of the time, though it does not require the absolute theoretical optimum. Obstacles should be avoided, but if they cannot be, then the algorithm needs to be smart enough to recognize this and deal with it. With some modifications, it works with non-stationary error topologies as well.

A novel path planning algorithm has been developed, in coordination with PSO, that generates a piece-wise linear path from a set of optimal waypoints. The path is guaranteed to be continuous, though the problem space itself may be discontinuous. The path avoids obstacles while minimizing total path distance.

The steps include setting up a region of interest, a start position, and a stop position, as well as initially random traversal waypoints. The optimization routine moves the way points around for each candidate solution and attempts to evolve the best path with regards to the reference cost function. The program calculates a path connecting all the waypoints from start to finish, and feeds this path to a cost function. The cost function determines various metrics such as length of path, collision with obstacles, work required to traverse the path, smoothness, weight on exploration of new territory vs. tracking the original outbound path, etc. The calculation of the optimal path is iterative; several rounds of feeding candidate solutions and using their associated costs to calculate new candidate solutions are required. The practical result of the pairing of this cost function strategy with PSO is that an optimal path is evolved much faster than random search, and completely forgiving of discontinuities.

The path planning prototype can be re-tasked on the fly and uses a unique “way point” optimization strategy. Unlike other optimization strategies, this one will work in a discontinuous environment with no modification necessary and is guaranteed to provide a continuous path from start to finish.

This work was done by Brian Birge of L-3 Communications for Johnson Space Center. MSC-24864-1

This Brief includes a Technical Support Package (TSP).

Surface Navigation Using Optimized Waypoints and Particle Swarm Optimization (reference MSC-24864-1) is currently available for download from the TSP library.

Please Login at the top of the page to download.