Personal tools
You are here: Home Courses Algorithms for Robot Motion Planning
« February 2023 »
Log in

Forgot your password?

Algorithms for Robot Motion Planning

Workshop (sadna)thumb thumb

Spring 2018


Course hours: Wednesday, 8:00-10:00
Location: Shreiber 008

Instructor: Dan Halperin, danha AT post tau ac il
Office hours by appointment

Teaching assistants: Michal Kleinbort (balasmic AT post tau ac il), Ravid Cohen (ravidcohn AT gmail com)



Paranoid Android

General information: Motion-planing algorithms compute collision-free motion paths for objects that move among obstacles.  They arise in robotics, graphical animation, surgical planning, navigation systems, computational biology and computer games, among other domains. In this workshop we will explore and apply algorithms for several robot systems, for example: (i) a fleet of blue robots that need to collect items in an environment cluttered with obstacles, while avoiding a fleet of red robots; (ii) a chopper that needs to automatically plan its route through a narrow valley; (ii) drones that need to carry out a prescribed task while avoiding obstacles on their way as well as other drones. 


Data structures, Algorithms, Software1

The first meetings

In the beginning of the workshop, we will present you with the very basics of algorithmic motion planning and lay out possible projects:

Other planned class meetings (more details below)

  • 11/4/18 
  • 30/5/18  


  • Chapter 7 in the following book:
    H. Choset, K. M. Lynch, S. Hutchinson, G. A. Kantor, W. Burgard, L. E. Kavraki and S. Thrun,
    "Principles of Robot Motion: Theory, Algorithms, and Implementations", MIT Press, 2005
  • M. Elbanhawi and M. Simic, 
    "Sampling-Based Robot Motion Planning: A Review" in IEEE Access, vol. 2, pp. 56-77, 2014 (link)
  • B. Raveh, A. Enosh and D. Halperin,
    "A Little More, a Lot Better: Improving Path Quality by a Path Merging Algorithm" in 
    IEEE Transactions on Robotics, 27(2): 365-371, 2011 (link)
  • J. P. van den Berg, D. Nieuwenhuisen, L. Jaillet and M. H. Overmars, 
    "Creating robust roadmaps for motion planning in changing environments", in IROS 2005, pp. 1053-1059 (link)

Course requirements and milestones 

  • Teamwork: The project is intended to involve a significant amount of teamwork. The recommended team size is three. Each group will choose a project among the list of projects, and submit the final project later in the summer.
  • Milestones: In order to make sure you successfully complete the project, you will be required to the following milestones:
          The schedule is tentative and subject to change; please stay tuned. 
    1. 14/3/18 - Teaming up and choosing a project:
      You will submit a short description of the selected project (title + one or two paragraphs with the basic details) in class.
    2. 11/4 - Class meeting (8:10- 10:00) after submitting an initial project plan (by e-mail):
      An initial description of the project and the work plan (2-3 pages):
      a. Title
      b. Description (~100-200 words) of the project's main idea.
      c. Brief description of project from a user point of view (input / output, etc.)
      d. Algorithmic details.
      e. The major programming tasks (engine, user interface, etc.) 
      f.  Milestones towards the final goal. 
      g. Tools that are going to help you program / run the project (libraries, programming languages, etc.).
      h. Open questions, conflicts and so on.
      Note: if you are considering two options, you can write more than one option and we can help you decide between those options.
    3. 30/5 - Class meeting (8:10 - 10:00): Project "Proof of Concept" / presentation / submission of final plan
      By this time, you will be required to show that the basic technical infrastructure of the project works (e.g. tools or programming libraries that need to be installed, etc.). We will give you a small programming task that you will need to accomplish by this time.
      In addition, you will present the final project plan in front of the class, and describe the task that you have accomplished. Please prepare to present your project and talk about it for 10-15 minutes. 
    4. 22/8 at 16:00, Save the date. Schreiber 309 - Basic prototype:  
      At this point in time, we will want to see your development progress, in order to make sure you are working in the right direction. You will show us a basic prototype of the final project. The prototype is expected to be a relatively small part of the final project (it is not expected to be fully functional). However, it should give a very good feeling of where you're heading.
    5. 16/9 or before- Submission of the final project + presentation: 
      Submitting a fully functional project, including documented code, a detailed user guide and a developer guide + presenting it to Michal. Each team is requested to coordinate with Michal a meeting of the team with Michal. 
      Developer guide - will include details about the algorithm, the implementation and the code design, to allow a new developer to approach your code. 
      > User guide - should outline the purpose of your project and its usage in a clear manner. 


We will use piazza platform for our forum discussions.

Use this link to sign up for this class:

Document Actions