OMPL Google Summer of Code 2013

We have been accepted as a mentoring organization for the Google Summer of Code 2013. Further contributions and enhancement proposals are welcome!

For future reference you may check the ​Google SoC website. You will find more information on their page on ​Advice for Students. The official ​timeline should be consulted for the other dates.

Motion Planning

Motion planning is a key problem in robotics. The basic version of the motion planning problem can be defined as finding collision-free paths between a start and a goal configuration of a robot. The problem gets much harder if additional constraints on the kinematics and dynamics of the robot are imposed. The complexity of the basic version of the problem is already PSPACE-hard, while some of the variants of the motion planning problem are even undecidable. Sampling-based algorithms have emerged as the state-of-the-art technique for motion planning. The Open Motion Planning Library (OMPL) contains efficient, yet general implementations of many of these algorithms. It is actively developed and is used to plan motions for many different robot hardware platforms (thanks to its integration with ROS, the Robot Operating System). There is a rapidly growing community of OMPL users, which we want to broaden through the Google Summer of Code projects listed below.

Project Ideas

Project: Add motion planning functionality to Blender/MORSE

Brief explanation: MORSE (Modular OpenRobots simulation Engine) is a Blender-based robotic simulator. It allows one to simulate robot motions with Blender’s built-in game engine. While new robots and associated controllers can be designed with MORSE, it is not possible to plan a motion that will take a robot from an initial state to a desired goal state. The Open Motion Planning Library (OMPL) is an ideal candidate to fill this gap in functionality. It is already used for this purpose within the significantly more complex Robot Operating System (ROS), which gives us confidence that the same can be done with MORSE. Additionally, we have extensive experience integrating OMPL with physics engines such as the Open Dynamics Engine (ODE) and Vortex (a commercial physics engine).

Expected results: an end user should be able to:

  1. Load a robot model and an environment model
  2. Specify a start and goal configuration
  3. Use OMPL to compute a feasible trajectory
  4. Play back the trajectory in Blender/MORSE

Knowledge Prerequisite: Python and ideally also C++ coding experience. Experience with modern version control systems recommended.

Skill level: medium to high.

Mentor: Mark Moll

Project: Create Matlab bindings for OMPL

Brief explanation: many engineering students and motion planning researchers have had little exposure to Python or C++, but have significant experience with Matlab. To make it easier for that audience to use motion planning algorithms, we would like to have Matlab bindings for the high-level OMPL functionality.

Expected results: A user should be able to instantiate models for car-like robots and kinematic chains and plan motions for them in Matlab/Octave.

Knowledge Prerequisite: C++ and Matlab experience.

Skill level: medium to high

Mentor: Mark Moll

Project: Data mining of benchmark results

Brief explanation: OMPL has built-in functionality for logging all kinds of diagnostic information that is stored in SQLite databases. Due to the random nature of the sampling in OMPL’s motion planning algorithms, many runs are necessary to say anything about an algorithm’s performance. The performance obviously also depends on the particular benchmark problem and algorithm parameter settings. We would like to know in what aspects a particular algorithm is different than others. That is, we want a characterization of an algorithm’s performance relative to others. This project involves data analytics, statistical testing, and (time permitting) machine learning on algorithm parameters that will optimize some performance metric.

Expected results: An end user should be able to interactively explore the databases and plot results, while the code would automatically highlight interesting trends. Ideally, this is done through a web interface using, e.g., Google Motion Charts, but we are open to people who are more familiar in doing this project with Qt-based GUI or using R.

Knowledge Prerequisite: basic knowledge of statistics and benchmarking. Knowledge of code profiling and optimization would be an added bonus (although this would not be the focus for this project).

Skill level: medium to high

Mentor: Ioan Sucan or Mark Moll

Project: User-guided motion planning

Brief explanation: We have examples motion planning problems that are difficult to solve for OMPL algorithms. Typically, this is due to some narrow passage that people might be able to recognize, but that is had to formalize in general. We would like to exploit human spatial reasoning skills in helping a motion planning algorithm solve a problem. We can show partial paths/solutions the algorithm has computed so far, and a user can provide hints on where and how the algorithm should search for a path. At the simplest level, a user can simply select points within narrow passages that a planner can try to connect to. Additionally, a user might be able to sketch motion segments or indicate that further exploration of some part of the search space is undesired (because it is a dead end).

Expected results: An implementation of some of the primitives above for use with rigid body motion planning. The existing PyQt-based GUI for OMPL can form a convenient starting point.

Knowledge Prerequisite: Knowledge of Python or C++, basic knowledge of PyQt or PySide.

Skill level: high

Mentor: Mark Moll or Ioan Sucan

Project: Use OMPL to plan motions in physics-based games

Brief explanation: Many games, even classic 2D games, use a simplified physics model that the user can control. This can be as simple as Pong or Breakout (from the stone age of computer games) to more realistic game engines used in, e.g. Quake. OMPL can treat the physics almost as a black box. OMPL can be used to “solve” some of these classic games, or we can define new physics-based games where OMPL is used to compute motions for a computer opponent. Marble mazes are an example of a real-world game that can be easily simulated and planned for.

Expected results: Either a “solver” for one or more computer games or a new game where the computer opponent uses OMPL to plan its moves. The physics in classic games may have to be modified to make it harder to solve.

Knowledge Prerequisite: Knowledge of C++, experience with game development.

Skill level: medium to high

Mentor: Mark Moll