TU Darmstadt / ULB / TUbiblio

Planning Formation Changes in Multi-Vehicle Systems based on Discrete-Continuous Linear Optimization

Bartsch, Stefanie (2010):
Planning Formation Changes in Multi-Vehicle Systems based on Discrete-Continuous Linear Optimization.
Darmstadt, Technische Universität Darmstadt, Department of Computer Science & Department of Mathematics, [Bachelor Thesis]

Abstract

The ?rst heterogeneous multi-vehicle path planning framework based on mixed-integer linear programming (MILP) including formation constraints is outlined with the possibility to model formation changes. Since MILP guarantee global optima, this approach suits for benchmarks against heuristic methods or to be embedded in model-predictive control approaches. Existing nonlinear path planning approaches including formation constraints are only locally optimal and therefore provide not necessarily the best solution. Proposals using hybrid system tools suffer from large computational efforts especially without good initial values. MILP solutions can then serve as initial estimates. The need to maintain and change formations, for instance in surveying large land areas while keeping in range of communication, induces the proposed framework. Further, it is capable to deal with inter-vehicle collision avoidance. A ?xed arrival time approach is considered to obtain fuel optimal paths. Formation topologies are modeled using a neighbor-referenced approach and are appended as constraints to the MILP . Two distinct ways to model pairwise distances are presented. To study systematically their ef?ciency concerning calculation time and achieved optimum, three example formations are implemented. The indirect distance determination is characterized by a strong restriction of the search space. In contrast, there is no limitation of the search space using the direct distance determination . Consequently, calcula- tion time increases substantially but the resulting paths require less fuel. The developed framework, including formation constraints, serves to plan formation changes.

Item Type: Bachelor Thesis
Erschienen: 2010
Creators: Bartsch, Stefanie
Title: Planning Formation Changes in Multi-Vehicle Systems based on Discrete-Continuous Linear Optimization
Language: English
Abstract:

The ?rst heterogeneous multi-vehicle path planning framework based on mixed-integer linear programming (MILP) including formation constraints is outlined with the possibility to model formation changes. Since MILP guarantee global optima, this approach suits for benchmarks against heuristic methods or to be embedded in model-predictive control approaches. Existing nonlinear path planning approaches including formation constraints are only locally optimal and therefore provide not necessarily the best solution. Proposals using hybrid system tools suffer from large computational efforts especially without good initial values. MILP solutions can then serve as initial estimates. The need to maintain and change formations, for instance in surveying large land areas while keeping in range of communication, induces the proposed framework. Further, it is capable to deal with inter-vehicle collision avoidance. A ?xed arrival time approach is considered to obtain fuel optimal paths. Formation topologies are modeled using a neighbor-referenced approach and are appended as constraints to the MILP . Two distinct ways to model pairwise distances are presented. To study systematically their ef?ciency concerning calculation time and achieved optimum, three example formations are implemented. The indirect distance determination is characterized by a strong restriction of the search space. In contrast, there is no limitation of the search space using the direct distance determination . Consequently, calcula- tion time increases substantially but the resulting paths require less fuel. The developed framework, including formation constraints, serves to plan formation changes.

Place of Publication: Darmstadt
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Simulation, Systems Optimization and Robotics Group
Date Deposited: 09 Jul 2019 10:46
Related URLs:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)

View Item View Item