tmkit  0.0.1-alpha1
A Task-Motion Planning Framework
 All Data Structures Files Functions Enumerations Enumerator Pages
TMKit Internals and Hacking

Table of Contents

This page describes some of the internals of TMKit, including design decisions and implementation choices. It is aimed at a developer who is not necessarily familiar with all the tools used to develop TMKit.

Library and Process Model 

          |------------------------------------|
          |            TMKit Process           |
          |------------------------------------|
          |------------------------------------|              |--------------------|
          |             TMKIT (SBCL)           |<------------>| SMT Solver Process |
          |                                    |   (SMT-LIB)  |--------------------|
          |                                    |
          |                                    |              |--------------------|
          |                                    |------------->|   Real-Time Land   |
          |------------------------------------|  T./M. Plan  |--------------------|
 |------->|             AMINO (SBCL)           |
 |        |------------------------------------|
 |        |             libamino.so            |
 |        |------------------------------------|
 |        | OMPL | FCL | GL/SDL2 | BLAS/LAPACK |
 |        |------------------------------------|
 |
 |
 |
 |
 |
 |  |--------------------|
 |->|  Blender Process   |
 |  |--------------------|
 |
 |  |--------------------|
 |->| C Compiler Process |
 |  |--------------------|
 |
 |  |--------------------|
 |->|   POV-Ray Process  |
    |--------------------|
TMKit runs as a single process communicating with several external tools. The primary TMKit process runs in SBCL. The primary process dynamically loads libamino.so (and related libraries) from the Amino package to handle geometric information. The libamino.so, etc. libraries link against several external libraries including OMPL for motion planning, the FCL for collision checking, and OpenGL / SDL2 for GUI rendering, and BLAS / LAPACK for linear algebra.


TMKit also forks several child processes. The SMT solver runs in a separate process, communicating with TMKit via the SMT-LIB format. Via code from Amino, TMKit uses Blender to convert meshes, a C compiler to compile meshes, and POV-Ray to produce high-quality rendered images.


The plan produced by TMKit will mostly likely need to be executed via a separate, real-time process because the TMKit process may impose unacceptable latices due to memory management and threading. Many of the routines from Amino, including the scene graph structure used by TMKit, are capable of low-latency, real-time performance.





Implementation Choices 


TMKit is implemented primarily in Common Lisp, interfaces with an external SMT Solver, makes heavy use of many C/C++ libraries. Each of these tools offers key advantages to satisfy the requirements of TMKit.


Why C/C++? 


Real-time constraints are an important consideration in robotics. To acheive acceptable latency, certain software modules, e.g., kinematic computations, must be implemented in a low-level language. C and C++ are the most widely-used and well-supported low-level languages. It is desirable to re-use as much of this existing, necessarily real-time code as possible.


Many other authors provide C or C++ libraries. TMKit makes heavy use of the Open Motion Planning Library, which provides a C++ interface.


Why SMT? 


Satisfiability Checking (SAT) underlies some of the most efficient task planning approaches. Many Satisfiability Modulo Theories (SMT) solvers offer the capability to perform incremental checking, which is useful for the repeated/alternation planning that Task-Motion planning sometimes requires. In addition, the "Theories" capability of SMT offers the potential to efficiently handle rich, non-boolean constraints in the robotics domain.


A number of of SMT solvers share the standard SMT-LIB input/output format. Using this standard format, we gain the flexibility to use different solvers and the ability to benefit from ongoing improvements to these tools.


Why Common Lisp? 


TL;DR: expressive for symbolic processing, plays well with C/C++ libraries, efficient performance.


Common Lisp is well-suited for the symbolic processing necessary in TMP. Symbolic Expressions are a builtin language type. You can see this expressivness in the TMKit source tree where the initial implementation of SATPlan required only ~300 lines of code.


The SBCL implementation can efficiently share data between Lisp and C functions, which improves interoperation with C/C++ libraries. Many other high-level language implementations cannot easily share such data because their (copying) garbage collector may move memory out from under a C function attempting to access it.


SBCL includes a high-quality compiler that produces efficient native code on all major CPU architectures.





APIs 


Amino 


TMKit makes heavy use of the Amino library, which defines the scene graph data structure and provides an interface to OMPL.


TMKit C API 


Parts of TMKit are implemented as a C library. In particular, plan file parsing is implemented in C so that this function can also be used by a separate real-time process that will execute the plan.


TMKit Lisp API 


The majority of TMKit is implemented in common lisp for the aforementioned reasons. Several functions are exported from the package, notably the primary entry point of the planner: `TMP-DRIVER'.


TMKit (CL)Python API 


Despite the productivy and performance advantages of common lisp, many potential users of TMKit may be unfamiliar with this language. Consequently, we also provide a CLPython-based interface for writing domain semantics definitions.





Code Organization 


The TMKit Source code is organized into several major modules.


SMT Solving 



PDDL and Task Planning 



Motion Planning 


All delegated to Amino and OMPL.


Task-Motion Planning 



Plan Files 


Note: Plan file parsing is implemented in C to support real-time processes executing plans.



Utility 






Development Environment 


A suitable environment will greatly speed up development.


Common Lisp blurs the distinctions between the typically separate edit-compile-test phases of software development by including the Lisp compiler in the Lisp runtime environment. (There is some myth that Lisp is interpreted. SBCL compiles all functions to native code.) In typical Lisp development, the program never necessarily terminates. Instead, individual functions are written/edited, compiled/loaded into the running program, and tested as needed. This interactive development style speeds up the edit-compile-test cycle from (often) minutes to (typically) seconds.


Taking advantage of the interactive Lisp development style requires support from the text editor to integrate with the Lisp system.


SLIME: The Superior Lisp Interaction Mode for Emacs 


SLIME provides integrated support for Lisp editing and interaction in Emacs.


The best way to setup SLIME is probably to install the Quicklisp package manager and follow their instructions to install SLIME via Quicklisp.


Alternatives to SLIME 


Some alternatives to SLIME exist, but these are much less widely used.






References 


TMKit 


Algorithm



Implementation



Common Lisp