Solving the empty space problem in robot path planning by mathematical morphology

Abstract

In this paper we formulate a morphological approach to path planning problems, in particular with respect to the empty-space problem, that is, the question of finding the allowed states for an object, moving in a space with obstacles. Our approach is based upon a recent generalization of mathematical morphology to spaces with noncommutative invariance groups. I. Introduction The problem of path planning is to find a path for an object, say a robot or a car, moving in a space (called `work space') with obstacles. The problem falls apart into two distinct subproblems [3]. First, the empty-space problem: find the allowed states of the robot 1 . Any possible configuration of the robot is represented as a point in a configuration space C, whose dimensionality equals the number of degrees of freedom of the robot [2]. Points in C such that a robot in that configuration would collide with any of the obstacles in work space are `forbidden'. The set of allowed points of C is called `empty-sp...