Velocity occupancy space: Autonomous navigation and dynamic obstacle avoidance with sensor and actuation error

In order to autonomously navigate in an unknown environment, a robotic vehicle must be able to sense obstacles, determine their velocities, then select and execute a collision-free path that will lead quickly to a goal. However, the perceived location and motion of the obstacles will be uncertain due to the limited accuracy of the robot's sensors. Thus, it is necessary to develop a system that can avoid moving obstacles using uncertain sensor data. The method proposed here is based on an occupancy grid ---which has previously been used to avoid stationary obstacles in an uncertain environment---in conjunction with velocity obstacles---which allow a robot to avoid well-known moving obstacles. The combination of these techniques leads to velocity occupancy space (VOS): a search space which allows the robot to avoid moving obstacles and navigate efficiently to a goal using uncertain sensor data.;However, the basic VOS concept assumes holonomic robots that are capable of instantaneous and error free velocity changes---capabilities that are not possessed by actual vehicles. Therefore, two extensions are derived by which VOS is adapted to work with actual robotic vehicles.;The first extension to VOS is for an acceleration controlled, differential drive robot. Two different techniques by which the differentially drive robot may approximate the velocity of a holonomic robot are derived and evaluated. They are then combined in order to allow the robot to select the best method based on the robot's current state.;The second extension to the basic VOS algorithm is designed to explicitly account for the actuation error experienced in typical robotic vehicles. The velocity obstacles are augmented to account for both the error in the robot's current position as well as the velocity error that will occur while the robot attempts to follow the command velocity so that these sources of error does not cause a collision.;Numerous simulation trials have been used to validate the original VOS concept as well as the two extensions. Experimental trials, with a typical, differentially driven robotic vehicle with actuation error, have demonstrated the success of VOS under real world conditions.