Motion planning for free-flying robots in dynamic and uncertain environments

This thesis presents a real-time motion-planning system for dynamic robots with dynamic constraints in non-static environments. A robot uses motion planning to generate a trajectory from where it is to where it needs to be. The class of dynamic robots includes ships, underwater vehicles, airplanes, helicopters, many types of ground vehicles, some robot arms, and free-flying space vehicles. These robots have equations of motion and bounded input forces that determine their possible motions through the environment.; Dynamic vehicles that operate in non-static environments require a fast yet capable motion-planning algorithm. The possibility of collision with a moving obstacle during trajectory generation requires that the planner plan quickly. At the same time, the equations of motion of the vehicle require that a trajectory specify velocity in addition to position and time to ensure that the path can be followed. A new path-generation algorithm was developed based on random-sampling planning techniques to solve these problems. A key feature of this algorithm is that the vehicle's equations of motion are naturally included in the sampling procedure. This limits the random search to possible robot motions, thereby decreasing the time required to find a path. When implemented for a two-dimensional free-flying robot, the algorithm proved capable of finding a trajectory within 0.5 s with a greater-than-99% probability for reasonable environments.; This new planning algorithm is used as the core of an intelligent autonomous planning system capable of operation in environments that contain unpredictably maneuvering obstacles. The planning system detects when the motions of the obstacles vary from those predicted at planning time and generates a new trajectory on-the-fly as necessary. It also incorporates a “Safe-Mode” planner that is used to generate safe paths should no path to the goal be found.; The complete planning system was experimentally validated on the Stanford University Aerospace Robotics Lab's free-flying-robot test bed. The planner enables the robot to avoid moving obstacles despite sensor noise, inter-object collisions and radical changes of obstacle direction. This is the first time that these capabilities have been achieved for a real dynamic robot.