Hierarchical path planning on probabilistically labeled polygons

In this paper, we consider the case of a robot that must nd ways in an initially unknown and often com-plex cross-country environment. Our approach relies on a particular model of the environment, built from 3D data: the environment is represented by a hier-archical polygonal structure, in which terrain classes probabilities are updated as the robot moves. We de-scribe how to dene traversability costs within such a structure, taking into account the label probabilities, and present how a shortest path search can produce a sequence of polygonal cells that must be crossed.