Planning High Quality Motion Paths for Robots, Workshop, Spring 2010

Software Workshop (sadna)

0368-3500-19

Instructor: Dan Halperin

Teaching Assistants:  Barak Raveh, Oren Zalz., Asaf Porat
Office Hours: Wed 14-16, Schreiber 08

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 planning high-quality motion paths. The quality of a motion path may be measured by the path length, smoothness, clearance from obstacles or even its physical energy. The students will apply motion-planning techniques to virtual robots, to physical (Lego NXT) robots, or to protein molecules.

Note to bioinformatics students: One of the fascinating applications of motion-planning algorithm is to simulate the motion of protein molecules. The amino-acids of the protein molecules are likened to rigid links, and the protein chain is free to rotate around its backbone torsion angles. Bioinformatics students may take this workshop as their 3rd year workshop. Along the way you will learn about both the state-of-the-art in algorithmic motion planning, and the important relation between protein motion and protein function. More information can be found in this link.

Link to Sadna 2009

Syllabus

In the beginning of the workshop, we will present you with the basics of algorithmic motion planning in a series of four lectures:

Link to Mini-Exercise (PDF format here ; submit by mail till Thursday, 25/3)

Course Requirements and Milestones

  • The final project will be submitted on the 1st of September, 2010 (details below).
  • 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 – see dates below.
  • Course staff: Except for doing the project for you, we are here to help you with any question. Please do not hesitate to contact the course’s team.
  • Milestones: In order to make sure you successfully complete the project, you will be required to the following milestones:
    1. 17/3 – Choosing a project:
      You will submit a short description of the selected project (title + one or two paragraphs with the basic details)
    2. 12/4 – Submitting an initial project plan (by e-mail):
      An initial description of the project and the work plan (2-3 pages Word document):
      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. 26/5 – 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.
      We will also ask you to submit the final project plan based on the initial plan, but we will expect more detailed solutions (and hopefully, there will be less open questions this time).
    4. 20/8 – Basic prototype: (date might change, please follow up)
      At this point in time, we will want to see your initial development, 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. 20/9 – Submission of a final project + presentation:
      Submitting a fully functional project, including documented code, a detailed user guide and a developer guide + presenting it to class.
      > Presentation (9:00 – 12:00, Schreiber 210) – 15 minutes EXACTLY for each group + 5 minutes time for questions (we have six groups – we will be strict on time). You should give a concise description of the project goals, the algorithm, the project implementation, the GUI and the final outcome.  You will need to design a set of problems where your projects succeeds and also show us the places where it fails.  Each group should give at least one non-trivial scene where the algorithm works, and one hard scene where the algorithm fails (more scenes are welcome). Please provide explanations as to why you think the algorithm succeeds in each case, and provide ideas for further improvements.
      > 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.

Project examples from the 2009 workshop

  1. Non holonomic motion planner
  2. Motion planning for a Lego-NXT robot

Reading Material

  • Chapter 7: Sampling-Based Algorithms in Principles of Robot Motion: Theory, Algorithms, and Implementations
    H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, and S. Thrun, The MIT Press, 2005.
  • Chapter 5: Sampling-Based Motion Planning in Planning Algorithms, S.M. LaValle, Cambridge University Press, 2006
    Web version

LegoNXT Robot – ABS Motion Planning Project

 This work is part of a High quality Motion Planning Workshop (spring-2009).

Project Goal:

Generate a path from source to target locations while avoiding obstacles, optimized in some aspects, for our constructed robot to follow.

The project included:

  • Designing and constructing a robot based on Lego (TM) parts with the MindStorm controller.
  • Designing an algorithm that calculates an efficient path according to parameters entered by the user.
  • Creating A second algorithm that converts the output of the first algorithm to a set of instructions for our robot to follow.

Project Milestones

  • Construction – we have decided to construct our robot as a Car-like robot. I.e. Forward motion generated in the front and steering generated in the back. This decision stemmed from our desire to make the project more interesting, compared to common robot construction models. Retrospectively this was proven to be harder than we thought, due to unexplained misbehavior by the robot from time to time (inaccuracies while following instructions).
  • Optimization aspects were selected:
    • Clearance – maximum distance to obstacles
    • Distance – minimal path distance
    • Turns – preference for turns that the robot performs well
  • Implementation & Design
    • Development/Final Environment: Our development environment consisted of “Google Sketchup” for designing the problem to be solved, “OOPSMP” libraries for existing motion planning algorithms and framework, “Microsoft Visual Studio” for coding, and “Bram NXT” library for controlling the robot.
    • Motion planning: Our approach was to use existing algorithms for motion planning, and hybridize their solution paths to a single path optimized for the aspects we selected, while prioritizing these aspects using weights given by the user.
    • Translation to robot control: We decided to address the issue of control by regarding the solution path as a path to follow, rather than a description of the robot’s exact state at a given time (which is the broadly accepted convention).

Results

Video of our robot in action

Non holonomic motion planner project

Authors : 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

Implementation

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.

Conclusions

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.

Movie

Press here to watch the movie

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content