%0 Conference Paper %B Proc. IEEE Int. Conf. on Robotics and Automation %D 2004 %T Motion Planning through Symbols and Lattices %A S. Pancanti %A L. Pallottino %A D. Salvadorini %A A. Bicchi %K Embedded Control %K Robotics %X

In this paper we propose a new approach to motion planning, based on the introduction of a lattice structure in the workspace of the robot, leading to efficient computations of plans for rather complex vehicles, and allowing for the implementation of optimization procedures in a rather straightforward way. The basic idea is the purposeful restriction of the set of possible inputfunctions to the vehicle to a finite set of symbols, or {\em control quanta},which, under suitable conditions, generate a regular lattice of reachable points. Once the lattice is generated and a convenient description computed, standard techniques in integer linear programming can be used to find a plan very efficiently. We also provide a correct and complete algorithm to the problem of finding an optimized plan (with respect e.g. to length minimization) consisting in a sequence of graph searches.

%B Proc. IEEE Int. Conf. on Robotics and Automation %P 3914-3919 %G eng