Personal tools
You are here: Home Courses Workshop Spring 2011 Projects MaBaker Motion Planner In a Dynamic Environment - MaBaker
« November 2022 »
Log in

Forgot your password?

Motion Planner In a Dynamic Environment - MaBaker

— filed under:

Project Goal - Generate a path for a Robot in a 2D Environment containing both Static & Dynamic obstacles.

In 2D Static worlds, finding a path from point A to point B is an interesting problem which can easily be solved. However, when there are also dynamic obstacles in the world, the problem may become very difficult. In our project we've tried to deal with both kind of obstacles.

Implementation & development Environment

The project was written in C++ using visual studio 2008, with support of the following software packages:

  • MFC - we used this package to create our GUI.
  • CGAL – for basic implementations & functions we used in our algorithms.

We've implemented and modified the PRM algorithm, and Zucker-kant Algorithm.  

Our solution is based on two main algorithms:

  • PRM – a motion planner algorithm for a static world.
  • Zucker & Kant – a motion planner algorithm for a dynamic world. The algorithm is actually takes convert the dynamic problem to a static problem.

We combined these two algorithms together with more improvements in order to get better results each one of them supply. More Details regarding implantation can be found in our Developer Guide & Project Presentation.


The resulting project

Our program is able to deal with a variety of scenarios. Additionally it gives the user full control on variety of variables and options our program support (such as create obstacles, change Robot velocity, size, expected time etc.). That helped us, for example, to see the cost-effectiveness of the different sampling methods. 


Visual results 

maze 1                      maze 2 

Demo Movies 


During the project we implemented some of the material which was presented during the semester (New algorithms for path planning ). We developed them in order to solve a bit more complicated idea that we came up with. Additionally creating the GUI forced us to deal with Analytical geometry problems.

We had to deal with a complicated project – specially the preplan of how we want to approach big project and how to split the work to sub destination in order to complete it efficiently.  

We believe we reached to a good and impressive outcome.

Additional Reading

  • User manual: link
  • Developer Guide: link
  • Project Presentation: link
  • K. Kant and S. Zucker. Toward efficient planning: the path-velocity decomposition. International Journal of Robotics Research, 5(3):72–89, 1986: link
  • Path Planning in Dynamic Environments, Jur Pieter van den Berg, May 1981: link

Authors : Omri Gindi, Roi Becker, Dvir Yosef

Document Actions