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