Motion Strategy Library Main Page

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 (FDP).

A. General Overview B. Downloading and Installation C. Help Getting Started D. Known Problems E. Revision History F. To-Do List G. Contributors

A. General Overview

MSL consists of seven C++ class hierarchies, each of which serving an independent purpose. The relationship between these classes is shown below.

This is not an inheritance diagram; it merely shows what information is passed from one hierarchy to another. Inheritance diagrams are included in the

• Model: 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 platforms.
• 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.

B. Downloading and Installation

Source distribution: [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 exemption addendum.

• Proximity Query Package (PQP) 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.

C. Help Getting Started

Several README files are contained within the distribution. These contain useful information regarding installation, running examples, and developing your own code that uses the library.

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 viewpoint.

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:

• 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.

The following files are optional:

• 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 planning step.
• Obst: A list of stationary obstacles, specified either as a list of polygons if GeomDim = 2, or a list of 3D triangles if GeomDim = 3.
• 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 are loaded.
• 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 RRTConCon.
• 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 rendering.
• ViewingDirection: The direction that the camera should point (a 3D vector)
• 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.

---

D. Known Problems

G. Contributors