Header menu link for other important links
X
Multi-Target Motion Planning Amidst Obstacles for Autonomous Aerial and Ground Vehicles
Published in Springer Netherlands
2018
Volume: 90
   
Issue: 3-4
Pages: 515 - 536
Abstract
The motion planning problem of a single autonomous vehicle having a minimum turn radius constraint, visiting an ordered sequence of targets in an environment with polygonal obstacles, is addressed. Two types of vehicles are considered: aerial/ground vehicle - described by the Dubins/Reeds-Shepp vehicle models, respectively. The problem is posed in the form of a search tree by using the obstacles’ vertices, vehicle’s initial configuration, and the set of target points as nodes. The tree’s arcs are represented by the Dubins/Reed-Shepp paths without terminal angle constraint (relaxed paths) connecting two adjacent nodes. These relaxed paths - connecting an initial configuration and a destination, are calculated using a feedback algorithm. Due to the computational complexity of the problem a genetic algorithm is proposed. Additionally, two deterministic search algorithms are presented. A quick heuristic greedy algorithm which uses the visibility graph distances for estimating the remaining vehicle path and an exhaustive algorithm which provides optimal solution trajectories. The performance of the algorithms is demonstrated and compared through sample runs and a Monte Carlo study. Results confirm that the heuristic algorithm provides relatively good solution for a small radius turn vehicle, while the genetic algorithm offers a good trade-off between computational load and performance. © 2017, Springer Science+Business Media B.V.
About the journal
JournalData powered by TypesetJournal of Intelligent and Robotic Systems: Theory and Applications
PublisherData powered by TypesetSpringer Netherlands
ISSN09210296
Open AccessNo
Concepts (16)
  •  related image
    Economic and social effects
  •  related image
    Genetic algorithms
  •  related image
    Heuristic algorithms
  •  related image
    Motion planning
  •  related image
    Trees (mathematics)
  •  related image
    Unmanned vehicles
  •  related image
    Vehicles
  •  related image
    Autonomous vehicles
  •  related image
    Computational loads
  •  related image
    FEEDBACK ALGORITHMS
  •  related image
    INITIAL CONFIGURATION
  •  related image
    MOTION PLANNING PROBLEMS
  •  related image
    Obstacles
  •  related image
    Optimal solutions
  •  related image
    TREE SEARCH
  •  related image
    Ground vehicles