EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
373. A new approach for inter-sample avoidance using an integer polytope formulation
Invited abstract in session MA-25: Discrete, continuous or stochastic optimization and control in networks, transportation and design I , stream Combinatorial Optimization.
Monday, 8:30-10:00Room: 011 (building: 208)
Authors (first author is the speaker)
| 1. | Johannes Schmidt
|
| Brandenburg University of Technology Cottbus - Senftenberg | |
| 2. | Armin Fügenschuh
|
| MINT, Brandenburg Technical University |
Abstract
To model the physics of the used vehicles in trajectory planning problems, Newton's equations of motion must be incorporated, discretized by numerical solution schemes. Thus, the position of the vehicle is in the model known only at a discrete set of points. Due to this lack of information, corner cutting can occur, i.e., the vehicle can abbreviate through an obstacle if it remains outside at every evaluation point again. Increasing the number of discrete time steps cannot resolve this problem completely and leads to higher computation times. To obtain always realistic solutions, corner cutting must be restricted, yielding so called inter-sample avoidance methods. We present a new approach to ensure inter-sample avoidance for polyhedral obstacles. The hyperplanes describing the obstacle divide the mission space into a set of subareas which can be encoded by binary vectors. These are used to ensure feasible movements without requiring more evaluation points or additional variables. We give a procedure to generate an integer polytope containing the feasible movements and derive an upper bound on the number of necessary constraints to describe it. The new approach is qualitatively tested against other inter-sample avoidance methods from the literature and its computational efficiency is studied in numerical experiments, using a mixed-integer linear program for trajectory planning of unmanned aerial vehicles and the state-of-the-art solver Gurobi.
Keywords
- Programming, Mixed-Integer
- Vehicle Routing
- Transportation
Status: accepted
Back to the list of papers