Optimal Planning with Differential Constraints using Heuristic-Based Search

Mancilla Caceres, Juan F.; Sanchez Plazas, Oscar

Permalink

https://hdl.handle.net/2142/48981 Copy

Description

Title

Optimal Planning with Differential Constraints using Heuristic-Based Search

Author(s)

• Mancilla Caceres, Juan F.
• Sanchez Plazas, Oscar

Issue Date

2010-05

Keyword(s)

• Motion Planning
• Dubins Car
• Differential Constraints
• Dynamic Programming

Abstract

In this work, we propose an approach to optimal control based on the A* algorithm. It employs a discrete approximation of the dynamic of the robot to estimate the cost-to-go function using the wavefront propagation algorithm. This simplified version of the problem provides a heuristic that is evaluated using linear interpolation. In addition, the density of exploration of the state space is bounded using a multi-scale scheme that increases the efficiency of the search. Two models were used to test this algorithm: the Dubins car and the Reed-Sheep car, both having a discrete set of actions. Preliminary results, using some basic polygonal environments, showed that the amount of states visited during the search is reduced by a significant factor; moreover, the cost of the solution is lower for the same resolution than for a systematic search algorithm. Although, the overhead for the computation of the heuristic is yet to be measured, this framework could be extended to more complex dynamic models to find feasible, close-to-optimal plans efficiently.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/48981

Owning Collections