Main Page Class Hierarchy Compound List File List Compound Members File Members
Motion Strategy Library Main Page
Motion Strategy Library
The Motion Strategy Library (MSL) allows easy development and testing
of motion planning algorithms for a wide variety of applications. It
was developed by Steven M. LaValle and his students, mainly from 2000
to 2003. It was the first open-source motion planning library and has
been updated as of July 2021.
The software architecture is object-oriented and the general design is
highly modular. It was developed on a Linux system using GNU C++,
STL, and the FOX GUI Toolkit. It
has been successfully compiled on various Windows systems as well.
The MSL is available as open source, free for both academic and
commerical use. Here is a copy of the licensing
agreement, which offers substantial freedom, to help spread
interest and applications of motion planning algorithms.
Presently MSL includes planners based on Rapidly-exploring Random Trees
(RRTs), Probabilistic Roadmaps (PRMs), and forward dynamic programming
MSL consists of seven C++ class hierarchies, each of which serving an
independent purpose. The relationship between these classes is shown
This is not an inheritance diagram; it merely shows what information
is passed from one hierarchy to another. Inheritance diagrams are
included in the Class Hierarchy documentation.
Each of the seven class hierarchies is briefly explained below:
These contain incremental simulators that model the
kinematics and dynamics of a variety of mechanical systems. The
methods allow planning algorithms to compute the future system state,
given the current state, an interval of time, and a control input
applied over that interval.
- Geom: These define the geometric
representations of all obstacles in the world, and of each part of the
robot. The methods allow planning algorithms to determine whether any
of the robot parts are in collision with each other or with obstacles
in the world.
- Problem: This is an interface
class to a planner, which abstracts the designer of a planning
algorithm away from particular details such as collision detection,
and dynamical simulations. Each instance of a problem includes both
an instance of Model and of Geometry. An initial state and final
state are also included, which leads to a problem to be solved by a
solver (typically a planning algorithm).
- Solver: There is currently
only one kind of solver, which is a hierarchy of planners.
A Solver is initialized with an
instance of Problem, and a method searches for a motion strategy that
solves a problem.
- Scene: This is an interface
class that computes configurations of all bodies to be displayed by a
rendering method. Scene receives most of its information directly
from Problem, but includes additional information relevant to
rendering, such as camera viewpoint.
- Render: This hierarchy of
classes contains different implementations of graphical rendering
requests. For example, when a graphical user interface (GUI) requests
that the a solution path is animated, a method in a Render class
displays the bodies in motion using configurations obtained from the
Scene class. Each derived class in Render corresponds to a different
graphics system. Presently, there are renderers for Open Inventor and
Open GL. The flexibility provided by these classes enables easy
extensions to be made for other graphics libraries and
- Gui: The graphical user interface
(GUI) is designed as a hierarchy of classes to enable specific user
interfaces to be designed for a variety of different motion strategy
problems and planning algorithms. Currently, there is one derived
class which serves as the GUI for all of the RRT-based planners. Each
instance of Gui includes an instance of an RRT Planner class and an
instance of a Render class. Using this design, the same basic GUI
design can be used, regardless of the particular rendering methods.
Here is the download information:
MSL Release 2.0a (04.07.21)
[gzipped tar file]
Linux binary distribution (Compiled using 64 bit Ubuntu 20.04):
[gzipped tar file]
The following libraries are used by MSL:
- FOX C++ GUI Toolkit
This library is free for use under an LGPL license with a relinking
- Proximity Query Package
This package was developed at the University of North Carolina, and is
free for noncommerical use. It performs efficient collision detection and
distance computations for a collection of triangles in a 3D world.
PQP is generally easy to install.
- Open GL
OpenGL (or an equivalent API, such as MesaGL) is required for 3D
rendering using the GL-based renderer. The needed libraries can be
obtained for free on most platforms (for example, they are included in
Ubuntu distributions). The library files are libglut, libGLU,
and libGL. The file libglut comes from the glut package, which
provides some GL utilities.
- Open Inventor
This library is required ONLY if you want to use the Inventor-based
renderer. It currently has all of the features of the GL-based renderer,
plus a few more. We recommend using this one if you can because
the shading is much more accurate. Open Inventor
is available as Open Source under the LGPL license.
Several README files are contained within the distribution.
These contain useful information regarding installation,
running examples, and developing your own code that uses the
Running the examples
In the default configuration, two executables are generated, plangl
and planleda. When running either of these, a path must be specified
that contains the problem. There are many example problems in the
data directory. To run one, type "plangl data/cage1".
The GuiPlanner window
The Construct button generates a planning graph, but does not attempt
to solve the problem. Plan attempts to find a path that connects the
InitialState to the GoalState (the PRM planner requires first using
Construct; RRT-based planners do not). If Plan fails, it can be
pressed again and the planner will continue to search using the
previous planning graphs as a starting point. The Planner menu allows
different planners to be attempted. The Display menu has functions
that show a solution path or show a 2D projection of the planning
graph. By default, the projection is shown using the first two state
varibles. In the planner control window the variables DrawIndexX
and DrawIndexY can be used to select other state variables to show in
the projection. The File menu contains many straightforward options
to read and write files. The Settings menu allows some planning
parameters to be adjusted, including DeltaT (the time step), NumNodes
(number of nodes to try to make each time Plan is pressed), and
GapDist (the distance threshold to use to declaring a connection has
been made in a dual tree search algorithm).
The GL renderer
The GL rendering window is primarily controlled using the render
control window. Some of the render control options can be performed
by pressing keys. Press 'h' to see a listing of these. Holding each
mouse button while moving allows a different type of change in the
The Inventor Renderer
You can grab onto the environment and spin it.
Making a new problem
Each problem is described by a directory full of files. Most of them
are ASCII files that are easily read and written. To make a
new example, some files are necessary, while others are optional.
Default values of parameters will be assumed when optional files are
not present. Some particular models might require files that are not
used in other models. For example, ModelLinear requires files "A" and
"B" which specify the matrices in the equation xdot = Ax + Bu. Other
than reading the code, an easy way to find out which files might be
needed for a particular model is to modify an example that has been
included in this distribution and uses the same model.
The following files are required for all examples:
The following files are optional:
- GeomDim: The dimension of the environment (2 or 3)
- ModelXXX: A file named exactly after the motion model to be used.
Examples are Model2DRigid and Model3DRigidMulti.
- GeomXXX: A file named exactly after the geometry model, such as
GeomPQP3DRigid for a rigid body made of triangles in a 3D world (with
PQP being used for collision detection).
- IntialState: The initial state for the problem.
- GoalState: The desired goal state.
- Robot: A model of the robot, specified either as a list of
polygons if GeomDim = 2, or a list of 3D triangles if GeomDim = 3.
For problems that involve multiple bodies, the robots are named
Robot0, Robot1, ..., Robotk, for k robots.
- ModelDeltaT: The time increment to be used for numerical integration
of the state transition equation (equations of motion).
- PlannerDeltaT: The time increment to be used for an incremental
- Obst: A list of stationary obstacles, specified either as a list
of polygons if GeomDim = 2, or a list of 3D triangles if GeomDim
- EnvList: A list of file names that correspond to stationary
geometric models that can be loaded and rendered (they are not used
for collision detection). If EnvList does not exist, then Obst is
loaded and rendered.
- BodyList: A list of file names that correspond to movable bodies.
If BodyList does not exist, then Robot, or Robot0, Robot1, ..., Robotk
- LowerState: The lowest possible state vector. Each element is
the smallest value for that state variable.
- UpperState: The highest possible state vector. Each element is
the largest value for that state variable.
- RRTXXX: A default planner selection, such as RRTExtExt or
- Inputs: A list of input vectors to be applied to the state
transition equation. By making this file, one can override the
defaults from the class constructor. For example, an car that can go
forward or reverse can be converted into a forward-only car by simply
changing this file.
- ViewingPosition: The (x,y,z) position of the camera to be used in
- ViewingDirection: The direction that the camera should point (a 3D
- ViewingOrientation: A possible rotation about the viewing
direction for the camera.
- LowerWorld: The smallest (x,y,z) value of the environment.
- UpperWorld: The largest (x,y,z) value of the environment.
- Holonomic: Let a planner know that the problem is holonomic with a
state transition equation of the form xdot = u. In this case,
performance can be greatly improved by ignoring the Inputs and
performing linear interpolation to generate local motions.
Extending existing models
Suppose that you would like to make your model derived class from
Model, or you would like to make your own variation of an RRT, PRM, or
FDP planner. This can be accomplished by writing very little code.
An example of how to make and use your own model is given in the
"tests" directory of the MSL distribution. Included in that
directory is a README that explains the examples. These are the
recommended way to use the MSL in a clean, object-oriented way.
If you write code this way and make some interesting contributions,
it will be easy for us to include it in future releases of the
library. If you simply hack away at the MSL source code, then it
will be nearly impossible to do this, and you will have difficulty
using upgraded versions of MSL.
- For solutions generated by any RRT planner with "Con" in the name, the
animated path might appear incorrect for nonholonomic planning problems.
This is because linear interpolation is used between far away states
that are given for rendering. The algorithms still correctly compute the
trajectory using numerical integration (only the display is wrong).
- Issues with 3D rotation remain (see revision history below).
We will likely switch to using quaternions in upcoming releases.
- The FDP planners do not actually produce approximately-optimal
solutions because the relax operation is not performed on the
members of the priority queue when a state is encountered multiple
- Peng Cheng
GL-based renderer. Some RRT classes.
- James Kuffner
Original Inventor renderer. Help with design of basic classes.
- Steve LaValle
Supervision of project. Most of the design and implementation of
basic classes. Implementation of most RRT, Model, and Geom classes.
- Steve Lindemann
Many bug fixes. Improved PRM implementations.
- Aswath Manohar
Many bug fixes. Enhanced Inventor renderer and FOX GUI.
- Benjamin Tovar
Improved installation scripts.
- Libo Yang
Performer renderer. Help with design of basic classes.
- Anna Yershova
3DChain, 3DTree classes.