Categories

# Synopsis

A new venture for the University of Bath and a collaboration with Mechanical and Electrical Engineering, the autonomous quad project aims to convert an ’off the shelf’ miniature quad bike to a driverless one. Generation of a least cost path to a pre-defined goal is required, which avoids known obstacles and will update for new obstacles detected during driving. The A* search algorithm is chosen and a comprehensive planner developed within MATLAB.

# Abstract

A path planner is required as part of an autonomous off-road vehicle project at the University of Bath, which is able to generate both an initial path (off-line) around obstacles to a goal, and update using data from camera detection during driving (on-line). The A* search algorithm is selected as the program foundation (including a custom cost function with terrain traversability and steering penalty) and developed using the MATLAB com- puting package. Limitations of the algorithm are clear, with a 45◦ angle step making the method unsuitable for driving autonomy. Following this conclusion the planner is improved and better tailored to our project, by testing three ‘angle-angle’ methods: Line of Sight Path Smoothing, Theta* and Field D* Interpolation. The two former are found to create the desired line, unbounded by the nodal grid, but as ‘short-cut’ techniques still provide no method of limiting the degree of turning.

Field D* interpolation is successfully implemented and forms the final planner in both off-line and on-line routines, generating a path in average times 1.8s and 50ms respectively, for a 0.1km2 workspace, 1m node size, and a 7.5◦ interpolation step; parameters found to be most suiting to our vehicle with a 22.5◦ steering limit. Heuristic weighting is found to improve searching time by 130%, using a value 20. Steering weight is less decisive and depends on the workspace configuration, a marginal inclusion in f(n) using a value 15 is seen to reduce drive time. All results are simulated due to the project and other sub-systems not yet being at a testing stage; real-world testing remains as the principle of any future work.

FinalReport

## 2 replies on “FYP: MATLAB A* Based Path Planner for Autonomous Off-Road Vehicle”

npsays:

Great work! could u explain how did you select the heuristic cost?
thanks..

Johnsays:

Thanks. The heuristic is just a simple Pythagorean estimate, with a weighting factor k:

$h(n') = k\cdot \sqrt{(x_g - x_{n'})^2 + (y_g - y_{n'})^2}$

Where $x_g, y_g$ are the goal coordinates and $x_{n'}, y_{n'}$ are the node to be explored.

I added other cost factors such as steering cost and traversability, along with the standard path cost but they are added as separate functions so be can excluded as and when.