01424nas a2200169   4500008004100000245004900041210004900090300001400139520089700153653002101050653001301071100001601084700001901100700001901119700001501138856010101153       2004                        eng d00aMotion Planning through Symbols and Lattices0 aMotion Planning through Symbols and Lattices  a3914-39193 a<p>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.</p>
10aEmbedded Control10aRobotics1 aPancanti, S1 aPallottino, L.1 aSalvadorini, D1 aBicchi, A.  uhttp://www.centropiaggio.unipi.it/publications/motion-planning-through-symbols-and-lattices.html