Multi-objective four-dimensional vehicle motion planning in large dynamic environments
Data(s) |
19/02/2011
|
---|---|
Resumo |
This paper presents Multi-Step A* (MSA*), a search algorithm based on A* for multi-objective 4D vehicle motion planning (three spatial and one time dimension). The research is principally motivated by the need for offline and online motion planning for autonomous Unmanned Aerial Vehicles (UAVs). For UAVs operating in large, dynamic and uncertain 4D environments, the motion plan consists of a sequence of connected linear tracks (or trajectory segments). The track angle and velocity are important parameters that are often restricted by assumptions and grid geometry in conventional motion planners. Many existing planners also fail to incorporate multiple decision criteria and constraints such as wind, fuel, dynamic obstacles and the rules of the air. It is shown that MSA* finds a cost optimal solution using variable length, angle and velocity trajectory segments. These segments are approximated with a grid based cell sequence that provides an inherent tolerance to uncertainty. Computational efficiency is achieved by using variable successor operators to create a multi-resolution, memory efficient lattice sampling structure. Simulation studies on the UAV flight planning problem show that MSA* meets the time constraints of online replanning and finds paths of equivalent cost but in a quarter of the time (on average) of vector neighbourhood based A*. |
Formato |
application/pdf |
Identificador | |
Publicador |
IEEE |
Relação |
http://eprints.qut.edu.au/40219/3/41990.pdf DOI:10.1109/TSMCB.2010.2061225 Wu, Paul P., Campbell, Duncan A., & Merz, Torsten (2011) Multi-objective four-dimensional vehicle motion planning in large dynamic environments. IEEE Transactions on Systems, Man and Cybernetics Part B: Cybernetics, 41(3), pp. 621-634. |
Direitos |
Copyright 2010 IEEE Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. |
Fonte |
Australian Research Centre for Aerospace Automation; Faculty of Built Environment and Engineering; School of Engineering Systems |
Palavras-Chave | #080101 Adaptive Agents and Intelligent Robotics #080110 Simulation and Modelling #090105 Avionics #090199 Aerospace Engineering not elsewhere classified #path planning #heuristic algorithms #multi-objective decision making #unmanned aerial vehicles |
Tipo |
Journal Article |