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 %0 Book Section %B Analysis and Design of Hybrid Systems 2003 %D 2003 %T Receding-Horizon Control of LTI Systems with Quantized Inputs %A B. Picasso %A S. Pancanti %A A. Bemporad %A A. Bicchi %E Gueguen Engell %E Zaytoon %K Embedded Control %K Robotics %XThis paper deals with the stabilization problem for a particular class of hybrid systems, namely discrete-time linear systems subject to a uniform (a priori fixed) quantization of the control set. Results of our previous work on the subject provided a description of minimal (in a specific sense) invariant sets that could be rendered maximally attractive under any quantized feedback strategy. In this paper, we consider the design of stabilizing laws that optimize a given cost index on the state and input evolution on a finite, receding horizon. Application of Model Predictive Control techniques for the solution of similar hybrid control problems through Mixed Logical Dynamical reformulations can provide a stabilizing control law, provided that the feasibility hypotheses are met. In this paper, we discuss precisely what are the shortest horizon length and the minimal invariant terminal set for which it can be guaranteed a stabilizing MPC scheme. The final paper will provide an example and simulations of the application of the control scheme to a practical quantized control problem.

%B Analysis and Design of Hybrid Systems 2003 %I Elsevier %P 259-264 %G eng %0 Book Section %B Hybrid Systems: Computation and Control %D 2002 %T Optimal control of quantized input systems %A S. Pancanti %A L. Leonardi %A L. Pallottino %A A. Bicchi %E C. Tomlin %E M. Greenstreet %K Embedded Control %K Robotics %XIn this paper we consider the problem of optimal control (specifically, minimum-time steering) for systems with quantized inputs. In particular, we propose a new approach to the solution of the optimal control problem for an important class of nonlinear systems, i.e. chained-form systems. By exploiting results on the structure of the reachability set of these systems under quantized control, the optimal solution is determined solving an integer linear programming problem. Our algorithm represents an improvement with respect to classical approaches in terms of exactness, as it does not resort to any a priori state-space discretization. Although the computational complexity of the problem in our formulation is still formally exponential, it lends itself to application of Branch and Bound techniques, which substantially cuts down computations in many cases, as it has been experimentally observed.

%B Hybrid Systems: Computation and Control %S Lecture Notes in Computer Science %I Springer-Verlag %C Heidelberg, Germany %V LNCS 2289 %P 351-363 %G eng %0 Conference Paper %B Proceedings of the NSF/ONR Workshop on Future Directions in Nonlinear Control of Mechanical Systems %D 2002 %T On Optimal Steering of Quantized Input Systems %A S. Pancanti %A L. Pallottino %A A. Bicchi %K Embedded Control %K Robotics %XIn this paper we consider the problem of optimal control (specifically, minimum-time steering) for systems with quantized inputs. In particular, we propose a new approach to the solution of the optimal control problem for an important class of nonlinear systems, i.e. chained-form systems. By exploiting results on the structure of the reachability set of these systems under quantized control, the optimal solution is determined solving an integer linear programming problem. Our algorithm represents an improvement with respect to classical approaches in terms of exactness, as it does not resort to any a priori state-space discretization. Although the computational complexity of the problem in our formulation is still formally exponential, it lends itself to application of Branch and Bound techniques, which substantially cuts down computations in many cases, as it has been experimentally observed.

%B Proceedings of the NSF/ONR Workshop on Future Directions in Nonlinear Control of Mechanical Systems %C Urbana, IL. %G eng %0 Conference Paper %B American Control Conference %D 2002 %T Safety of a decentralized scheme for Free-Flight ATMS using Mixed Integer Linear Programming %A L. Pallottino %A A. Bicchi %A S. Pancanti %K Embedded Control %K Robotics %XIn this paper we consider policies for free-flight management of air traffic. We consider instantaneous and bounded heading angle deviation as conflict avoidance maneuvers. The corresponding model, resulting in a Mixed Integer Linear Programming (MILP) problem allow to solve both conflict detection and conflict resolution problems. The developed algorithm proved successful in a centralized implementation with a large number of cooperating aircraft. However, the application of such algorithm to a Free Flight environment, where cooperation can only be expected from neighboring aircraft, poses many challenges. We consider a model of the decentralized conflict resolution strategy that is based on a hybrid system, and sufficient conditions under which a 3-aircraft Free Flight MILP-based scheme guarantees safety of flight are provided.

%B American Control Conference %P 742-747 %8 May %G eng