This software finds the shortest paths between configurations for the Dubins'
car [Dubins51], the forward only car-like vehicle with a constrained turning
radius. A good description of the equations and basic strategies for doing this
are described in section 15.3.1 "Dubins Curves" <http://planning.cs.uiuc.edu/node821.html>
of the book "Planning Algorithms"
[LaValle06]_.
The approach used to find paths is based on the algebraic solutions published in [Shkel01]_. However, rather than using angular symmetries to improve performance, the simpler approach to test all possible solutions is used here.
|build_status| |coverage| |license|
The recommended approach is to add dubins.c
and dubins.h
to your project
and compile with an appropriate build system.
The repository includes a basic cmake example that demonstrates how to build and test the library.
The following code snippet demonstrates how to generate intermediate points along the shortest path between a pair of configuration (x, y, theta).
.. code-block:: c
#include "dubins.h"
#include <stdio.h>
int printConfiguration(double q[3], double x, void* user_data) {
printf("%f, %f, %f, %f\n", q[0], q[1], q[2], x);
return 0;
}
int main()
{
double q0[] = { 0,0,0 };
double q1[] = { 4,4,3.142 };
double turning_radius = 1.0;
DubinsPath path;
dubins_shortest_path( &path, q0, q1, turning_radius);
dubins_path_sample_many( &path, 0.1, printConfiguration, NULL);
return 0;
}
The following image shows some example paths, and the heading of the vehicle at each of the intermediate configurations.
.. image:: ./docs/images/samples.png
MathWorks FileExchange <http://www.mathworks.com.au/matlabcentral/fileexchange/40655-dubins-curve-mex>
_GitHub <https://github.com/AndrewWalker/pydubins>
and on PyPI <https://pypi.python.org/pypi/dubins/>
If you would like to cite this library in a paper or presentation, the following is recommended:
.. code-block:: bibtex
@Misc{DubinsCurves,
author = {Andrew Walker},
title = {Dubins-Curves: an open implementation of shortest paths for the forward only car},
year = {2008--},
url = "https://github.com/AndrewWalker/Dubins-Curves"
}
The Dubin's curves library was completed as one small part of [Walker11]_. New contributions or bug fixes are welcome.
Key contributors to the project include:
MIT License. See LICENSE.txt <LICENSE.txt>
_ for details.
.. [Dubins51] Dubins, L.E. (July 1957). "On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents". American Journal of Mathematics 79 (3): 497–516 .. [LaValle06] LaValle, S. M. (2006). "Planning Algorithms". Cambridge University Press .. [Shkel01] Shkel, A. M. and Lumelsky, V. (2001). "Classification of the Dubins set". Robotics and Autonomous Systems 34 (2001) 179–202 .. [Walker11] Walker, A. (2011). "Hard Real-Time Motion Planning for Autonomous Vehicles", PhD thesis, Swinburne University. .. [Smart08] Royce, S. (2008). "Evolutionary Control of Autonomous Underwater Vehicles". PhD thesis, RMIT
.. |build_status| image:: https://secure.travis-ci.org/AndrewWalker/Dubins-Curves.png?branch=master :target: https://travis-ci.org/AndrewWalker/Dubins-Curves :alt: Current build status
.. |coverage| image:: https://codecov.io/gh/AndrewWalker/Dubins-Curves/branch/master/graph/badge.svg :target: https://codecov.io/gh/AndrewWalker/Dubins-Curves :alt: Code coverage shield
.. |license| image:: https://img.shields.io/badge/License-MIT-blue.svg :target: http://opensource.org/licenses/MIT :alt: license shield