Files in this item



application/pdfreport.pdf (1MB)
Main articlePDF


Title:Optimal Planning with Differential Constraints using Heuristic-Based Search
Author(s):Mancilla Caceres, Juan F.; Sanchez Plazas, Oscar
Subject(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.
Issue Date:2010-05
Genre:Technical Report
Publication Status:unpublished
Peer Reviewed:not peer reviewed
Date Available in IDEALS:2014-05-05

This item appears in the following Collection(s)

Item Statistics