Personal tools
You are here: Home Courses Workshop Spring 2009 Final projects Non holonomic motion planner project
« November 2022 »
Log in

Forgot your password?

Non holonomic motion planner project

Narrow SceneAuthors : Bosmat Eldar, Itamar Berger, Gal Zohar


This project is part of the high-quality motion paths for robots workshop, Spring 2009 


Project Goal  

Generating high-quality paths for non-holonomic robots.

In 2D worlds, finding a path from point A to point B is an interesting problem which can easily be solved. However, when there are limitations on the robot's movement, the problem may become difficult. In this project we've tried to deal with the limitations of cars' movement. Cars are non-holonomic, so actions such as parking or making a sharp turn are not always trivial. A typical GPS doesn't take these limitations into account.

In order to make high quality paths, we've defined several criteria for path quality: length, smoothness, clearance and minimizing reverse and steering amount.


The resulting project

We've examined the solutions currently suggested for this problem over the net, and a particular article appeared to be a good start for our basic demands -  "Randomized Motion Planning for Car-like Robots with C-PRM" by Guang Song and Nancy M. Amato from Texas A&M University. [PDF]

The C-PRM algorithm provides us the ability to control the preferred paths procedure. We used its basic structure to achieve our quality criteria.

The results were encouraging, however, we thought the Hybrydization method we'd learned in the workshop might improve the path quality. Merging the methods wasn't trivial. The combination of the paths required some creativity because the C-PRM algorithm wasn't meant to support it.
This optimization improved the results in every quality measure, but, as expected,
solving the problem multiple times reqiured that much more time.

We noticed that custom optimizations can assist in specific situations,
so we've added some more optimizations for situations such as parking and narrow passage.

Finally , the resulting project is a fully GUI standalone application which contains a
"Scene Creator" – a painter program for creating 2d worlds ( and saving as XML files) 
made from polygons, and the main program – an impressive non-holonomic motion planner.

Visual results

green : start point

red : end point

SmallRooms Scene

Maze SceneSmall Scenes


The project was written in C++ with support of the following software packages:

  • OOPSMP – we used this package as a basic framework for our project.
    This package contains some useful tools such as Graph structures,
    Search Algorithms, State Sampler ,XML reader, basic GUI etc.
  • PQP – Collision Detector , assisted in finding collision and distance measurements between polygons.
  • Triangulate – used for triangulate the polygons for the collision detector.  
  • QT – used for 2D GUI implementation.
  • OpenGL – used to draw the problem. 

We've implemented and modified the C-PRM algorithm.

More Details regarding implantation can be found in our Developer Guide Manual.


We've learned a lot in this workshop. We've been introduced to the interesting field of MotionPlanning -
A broad field with much room for innovation.
In this project we were required to deal with a large software package and a lot of self learning.

We were given a great deal of freedom and support throughout the project.
We believe our final results are interesting and perhaps even innovative in the field of car motion planning.




Document Actions