Many of the applications that have been proposed for future small unmanned aerial vehicles (UAVs) are at low altitude in areas with many obstacles. A vital component for successful navigation in such environments is a path planner that can find collision free paths for the UAV. Two popular path planning algorithms are the probabilistic roadmap algorithm (PRM) and the rapidly-exploring random tree algorithm (RRT).Adaptations of these algorithms to an unmanned autonomous helicopter are presented in this thesis, together with a number of extensions for handling constraints at different stages of the planning process…
Contents
1 Introduction
1.1 Contributions
1.2 The WITAS UAV Project
1.3 Publications
1.4 Outline of the thesis
2 The Path Planning Problem
2.1 Basic Concepts
2.1.1 Work Space
2.1.2 Configurations
2.1.3 State
2.1.4 Path Description
2.2 Constraints
2.2.1 Obstacle Constraints
2.2.2 Motion Constraints
2.3 Path Planning
2.4 Completeness, Optimality and Complexity
3 Early Path Planning Algorithms
3.1 Classical Roadmap Algorithms
3.2 Cell Decomposition
3.3 Potential fields
4 Sampling-based Path Planning Algorithms
4.1 Probabilistic Roadmaps
4.1.1 The Probabilistic Roadmap Algorithm
4.1.2 Improved Roadmap Construction
Sampling near obstacles
Focus on Difficult Areas
Visibility-based PRMs
4.1.3 Lazy PRM
4.1.4 Theoretical Results
4.2 Rapidly Exploring Random Trees
4.2.1 Constructing RRTs
4.2.2 Using RRTs for Path Planning
4.2.3 Theoretical Results
4.2.4 Optimization of paths
4.2.5 Probabilistic Roadmaps of Trees
4.3 Kinematic constraints
4.3.1 Kinematic Path Planning with PRM
4.3.2 Customizable PRM
4.3.3 Multi-Level Handling of Nonholonomic Constraints
4.4 Dynamic Constraints
4.4.1 RRTs for Kinodynamic Motion Planning
4.4.2 Application to Autonomous Helicopters
4.4.3 Other Applications
4.5 Time and Change
4.5.1 Moving obstacles
4.5.2 Roadmap Updates
5 Path Planning Framework
5.1 Path Planner Overview
5.2 Motion Constraints
5.2.1 State Space Roadmap
5.2.2 Multi-level Path Planning
5.2.3 Related Work
5.3 Runtime Constraints
5.3.1 PRM Planner with Runtime Constraints
5.3.2 Implemented Runtime Constraints
5.3.3 Repairing Broken Roadmap Connectivity
5.3.4 Related Work
5.4 Post Processing the Plan
6 Obstacle Constraints
6.1 The Environment and Helicopter Model
6.2 The Collision Checker
6.2.1 OBBs
6.2.2 Building the OBB tree
6.2.3 Intersection with OBB Trees
6.3 Runtime Constraints
7 System Integration
7.1 System Architecture
7.2 Local Path Planning and Control
7.2.1 Curve Description
7.2.2 Trajectory-Following Controller
7.2.3 Proportional Navigation
7.3 Plan Execution
8 Flight Tests with the Helicopter
8.1 Interactive Camera Positioning
8.2 Use of Runtime Constraints
8.3 Photogrammetry
9 Comparisons between Path Planning Algorithms
9.1 Method
9.1.1 World models
9.1.2 Implementations
PRM: Roadmap Generation
PRM: Runtime Planner
RRT planner
Collision Checker
9.1.3 Test Setup
9.2 Comparisons between PRM and RRT
9.2.1 Completeness
9.2.2 Planning Time
9.2.3 Path Length
9.2.4 Discussion
9.3 PRM with Runtime Constraints
9.3.1 Timing Tests
9.3.2 Repairing Broken Roadmap Connectivity
9.4 Approaches for Handling Motion Constraints
9.4.1 Roadmap Size
9.4.2 Planning Time
9.4.3 Remaining Sharp Corners
9.4.4 Discussion
10 Conclusions
10.1 Integration with the Helicopter Platform
10.2 Changing Constraints
10.3 Mission Planning
Author: Pettersson, Per Olof
Source: Linköping University
Download URL 2: Visit Now