Path Planning Algorithms for a Car-Like Robot visiting a set of Waypoints with Field of View Constraints

摘要

This article considers two variants of a shortest path problem for a car-like robot visiting a set of waypoints. The sequence of waypoints to be visited is specified in the first variant while the robot is allowed to visit the waypoints in any sequence in the second variant. Field of view constraints are also placed when the robot arrives at a waypoint, i.e., the orientation of the robot at any waypoint is restricted to belong to a given interval of angles at the waypoint. The shortest path problem is first solved for two waypoints with the field of view constraints using Pontryagin's minimum principle. Using the results for the two point problem, tight lower and upper bounds on the length of the shortest path are developed for visiting n points by relaxing the requirement that the arrival angle must be equal to the departure angle of the robot at each waypoint. Theoretical bounds are also provided on the length of the feasible solutions obtained by the proposed algorithm. Simulation results verify the performance of the bounds for instances with 20 waypoints.