The Find-Path Problem in the Plane

Abstract

This paper presents a fast heuristic algorithm for planning collision-free paths of a moving robot in a cluttered planar workspace. The algorithm is based on describing the free space between the obstacles as a network of linked cones. Cones capture the freeways and the bottle-necks between the obstacles. Links capture the connectivity of the free space. Paths are computed by intersecting the valid configuration volumes of the moving robot inside these cones and inside the regions described by the links.