The cl-rrt Reference Manual

Table of Contents

The cl-rrt Reference Manual

This is the cl-rrt Reference Manual, version 0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Dec 22 12:44:41 2020 GMT+0.

1 Introduction

#+LINK: hs http://www.lispworks.com/reference/HyperSpec//%s

* CL-RRT - Common Lisp implementation of RRT (Rapidily exploring Random Tree)

[[https://raw.github.com/guicho271828/cl-rrt/master/figure.png]]

RRT is a fast probabilistic multidimentional path-plannning algorithm
introduced by S.M.LaValle (1). It now has a widespread use in robotics
and now able to handle the real time systems such as automatic car
driving AI. Also, it has various extentions and optimization methods
(but not yet implemented here) such as:

+ MP-RRT -- optimizing version of RRT
+ RR-belief-tree -- RRT under uncertainity
+ RRG -- use a graph structure instead of a tree
+ RRT* -- optimizing version of RRT
+ St-RRT -- temporal algorithm

The above image is a test result of a motion planner from the
start(red) to the end (blue). The path is avoiding the collision to
the randomly generated obstacles.
Note that the path is not optimized -- RRT gains speed sacrificing the
cost of the path.
The source is in =t/= .


(1) S.M. LaValle and J.J. Kuffner. Randomized kinodynamic
planning. /The International Journal of Robotics Research/, Vol. 20,
No. 5, pp. 378–400, 2001.

** Recent changes

+ =edge-prohibited-p= and =finish-p= is now keyword arguments. (2013
  March 1st)
+ Supported R-tree based nearest neighbor search (2013 Dec 8th).
  + It's computational order is smaller than the other trivial
    implementations, but in practice it may be slow sometimes
    (especially for the small problems)

** Future extension

+ improvements in the nearest search.
  + with R-tree or kd-tree

** Dependencies

This library is at least tested on implementations listed below:

+ SBCL 1.1.2 on X86-64 Linux  3.2.0-39-generic (author's environment)
+ Clozure Common Lisp Version 1.9-r15757 on X86-64 Linux  3.2.0-39-generic (author's environment)

Also, it depends on the following libraries:

+ ITERATE  ::
    Jonathan Amsterdam's iterator/gatherer/accumulator facility

+ ALEXANDRIA  ::
    Alexandria is a collection of portable public domain utilities.

+ CL-ANNOT by Tomohiro Matsuyama ::
    Python-like Annotation Syntax for Common Lisp

+ ANAPHORA  ::

** Installation

+ Quicklisp loadable. First open slime REPL.
+ =(ql:quickload :cl-rrt)= and the library will be installed along with all
  the dependencies.

** Author

+ Masataro Asai (guicho2.71828@gmail.com)
+ Univ. Tokyo -> Grad. school of Tokyo University

* Concepts and API


The key concept in RRT is C-space and State-space.

C-space (configuration space) is a multidimentional space which
represents *the state of a robot*. For example, a human arm has 6
degrees of freedom and its C-space also has at least 6
dimension. However, in this example the dimension of C-space can be up
to 18 because it is allowed to have the differencial factor
for each coordinate -- its velocity and the accelaration.

State-space is also a multidimentional space. It contains all the
values in C-space and also *the controls of the robot*. A control is
an output of the robot and it is different from the speed and the
accelaration. For example, if you implement a car AI, the actual acceleration would
not nessesarily match the output of the engine because there is a
drift between the tire and the ground.

In each step of a search, RRT randomly choose a point in a State-space
and create a node. It search for the nearest
node in the existing tree to the new node (_NNS:Nearest Neighbor Search_),
using the user-specified distance function,
and the found node is connected with the new node.
The search finishes when a certain criteria is met.

Each new point subdivides the Voronoi Cell in the State-space.
Since the larger Volonoi Cell more likely contains the new node,
the direction of the search is heavily biased to the less-searched space.

* Example and Tutorial

Not written yet. See =t/= for example, there is a testing code.
To run a test, =(asdf:load-system :cl-rrt-test)=.

* API

See [[./references.org]] .

* Copyright

Copyright (c) 2013 Masataro Asai (guicho2.71828@gmail.com)

* License

Licensed under the LLGPL License.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 cl-rrt

Author

Masataro Asai

Contact

guicho2.71828@gmail.com

License

LLGPL

Description

Common Lisp implementation of RRT (Rapidily exploring Random Tree), a fast probabilistic multidimentional path-plannning algorithm.

Version

0.1

Dependencies

• iterate
• alexandria
• cl-syntax-annot
• anaphora

Source

cl-rrt.asd (file)

Component

src (module)

3 Modules

Modules are listed depth-first from the system components tree.

3.1 cl-rrt/src

Parent

cl-rrt (system)

Location

src/

Components

• package.lisp (file)
• rrt.lisp (file)
• helper.lisp (file)
• rrt-tree-list.lisp (file)
• rrt-tree-tree.lisp (file)

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.

4.1 Lisp

4.1.1 cl-rrt.asd

Location

cl-rrt.asd

Systems

cl-rrt (system)

4.1.2 cl-rrt/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

cl-rrt

4.1.3 cl-rrt/src/rrt.lisp

Dependency

package.lisp (file)

Parent

src (module)

Location

src/rrt.lisp

Exported Definitions

• child-not-found (condition)
• children (method)
• (setf children) (method)
• configuration-space-distance (generic function)
• connect (function)
• content (method)
• (setf content) (method)
• count-nodes (generic function)
• count-nodes (method)
• disconnect (function)
• finish-node (method)
• (setf finish-node) (method)
• insert (generic function)
• insert (method)
• insert (method)
• leafs (generic function)
• leafs (method)
• map-rrt-tree-content-recursively (function)
• map-rrt-tree-node-recursively (function)
• mapc-rrt-tree-content-recursively (function)
• mapc-rrt-tree-node-recursively (function)
• nearest-node (generic function)
• nnext-branch (function)
• parent (method)
• (setf parent) (method)
• result-path (function)
• result-path-nodes (function)
• root (method)
• (setf root) (method)
• rrt-node (function)
• rrt-search (function)
• rrt-tree-mixin (class)
• rrt-tree-node (class)
• split-branch-rrt-search (function)

4.1.4 cl-rrt/src/helper.lisp

Dependency

rrt.lisp (file)

Parent

src (module)

Location

src/helper.lisp

Exported Definitions

• adopt-children (function)
• neglect (function)
• orphanize (function)

4.1.5 cl-rrt/src/rrt-tree-list.lisp

Dependency

helper.lisp (file)

Parent

src (module)

Location

src/rrt-tree-list.lisp

Exported Definitions

• insert (method)
• nearest-node (method)
• nodes (method)
• (setf nodes) (method)
• rrt-tree-list (class)

Internal Definitions

%nearest-node-list (function)

4.1.6 cl-rrt/src/rrt-tree-tree.lisp

Dependency

rrt-tree-list.lisp (file)

Parent

src (module)

Location

src/rrt-tree-tree.lisp

Exported Definitions

• count-nodes (method)
• leafs (method)
• nearest-node (method)
• nodes (method)
• rrt-tree-tree (class)

5 Packages

Packages are listed by definition order.

5.1 cl-rrt

Source

package.lisp (file)

Nickname

rrt

Use List

• iterate
• anaphora
• alexandria
• cl-annot.slot
• cl-annot.doc
• cl-annot.class
• cl-annot
• cl-syntax
• common-lisp

Exported Definitions

• adopt-children (function)
• child-not-found (condition)
• children (generic function)
• children (method)
• (setf children) (method)
• (setf children) (generic function)
• configuration-space-distance (generic function)
• connect (function)
• content (generic function)
• content (method)
• (setf content) (method)
• (setf content) (generic function)
• count-nodes (generic function)
• count-nodes (method)
• count-nodes (method)
• disconnect (function)
• finish-node (generic function)
• finish-node (method)
• (setf finish-node) (method)
• (setf finish-node) (generic function)
• insert (generic function)
• insert (method)
• insert (method)
• insert (method)
• leafs (generic function)
• leafs (method)
• leafs (method)
• map-rrt-tree-content-recursively (function)
• map-rrt-tree-node-recursively (function)
• mapc-rrt-tree-content-recursively (function)
• mapc-rrt-tree-node-recursively (function)
• nearest-node (generic function)
• nearest-node (method)
• nearest-node (method)
• neglect (function)
• nnext-branch (function)
• nodes (generic function)
• nodes (method)
• nodes (method)
• (setf nodes) (method)
• (setf nodes) (generic function)
• orphanize (function)
• parent (generic function)
• parent (method)
• (setf parent) (method)
• (setf parent) (generic function)
• result-path (function)
• result-path-nodes (function)
• root (generic function)
• root (method)
• (setf root) (method)
• (setf root) (generic function)
• rrt-node (function)
• rrt-search (function)
• rrt-tree-list (class)
• rrt-tree-mixin (class)
• rrt-tree-node (class)
• rrt-tree-tree (class)
• split-branch-rrt-search (function)

Internal Definitions

%nearest-node-list (function)

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

6.1 Exported definitions

6.1.1 Functions

Function: adopt-children NEW-PARENT OLD-PARENT

HELPER FUINCTION: removes the children of old-parent and the new-parent takes all of them.

Package

cl-rrt

Source

helper.lisp (file)

Function: connect PARENT CHILD

connect two nodes as a parent and a child.

Package

cl-rrt

Source

rrt.lisp (file)

Function: disconnect PARENT CHILD

disconnect a parent and its child. signals CHILD-NOT-FOUND < SIMPLE-CONDITION.

Package

cl-rrt

Source

rrt.lisp (file)

Function: map-rrt-tree-content-recursively NODE FN

Map over the contents of RRT-TREE-NODEs of the tree and return each result in a nested tree
with the same structure as the original random-tree.

Package

cl-rrt

Source

rrt.lisp (file)

Function: map-rrt-tree-node-recursively NODE FN

Map over the RRT-TREE-NODEs of the tree and
return the results in a nested cons tree
with the same structure as that of the original random-tree.

Package

cl-rrt

Source

rrt.lisp (file)

Function: mapc-rrt-tree-content-recursively NODE FN

Mapc over the contents of RRT-TREE-NODEs ofthe tree and returns nil. Only for the side effect.

Package

cl-rrt

Source

rrt.lisp (file)

Function: mapc-rrt-tree-node-recursively NODE FN

Mapc over the RRT-TREE-NODEs of the tree and returns nil. Only for the side effect.

Package

cl-rrt

Source

rrt.lisp (file)

Function: neglect PARENT

HELPER FUNCTION: disconnect all children from the specified parent

Package

cl-rrt

Source

helper.lisp (file)

Function: nnext-branch TREE

TREE -> TREE
Destructively modifies and return an RRT-TREE. If the
‘tree’ has a finish node, it finds a path from the root to
the end and then replace the root with the next node in that path. Otherwise it choose one child of the root at random and replace the root with it. In both cases the new root is orphanized.

Package

cl-rrt

Source

rrt.lisp (file)

Function: orphanize CHILD

HELPER FUNCTION: ensure a node doesn’t have a parent

Package

cl-rrt

Source

helper.lisp (file)

Function: result-path TREE

TREE -> (list (node V))
Returns a list of C-space points of the computed paths
from the root to the end. Returns nil if the path was not found. The list contains the root of the tree.

Package

cl-rrt

Source

rrt.lisp (file)

Function: result-path-nodes TREE

TREE -> (list V)
Returns the nodes of the computed path in a list, from
the root to the end. Returns nil if the path was not found. The list contains the root of the tree.

Package

cl-rrt

Source

rrt.lisp (file)

Function: rrt-node CONTENT

Identical to =(make-instance ’rrt-tree-node :content content)=

Package

cl-rrt

Source

rrt.lisp (file)

Function: rrt-search RANDOM-GENERATOR NEW-V-GENERATOR &key EDGE-PROHIBITED-P FINISH-P START-V TREE TREE-CLASS TREE-CLASS-OPTIONS MAX-NODES MAX-ITERATION RUN-ON-NODE

RRT-search function.
let V as a type variable.

+ V :: a vector class which represents the point in C-space. (configuration-space-distance V V) should return a number. + (node V) :: an rrt-tree-node instance whose ‘content’ slot is V. non-holonomic parameters like velocity and acceralation should be stored within (node V), not in V.

‘rrt-search’ returns the result tree as its primary value. The secondaly value is the total number of the nodes, and third value is the number of iteration done in the search.

the arguments should be of types as listed in the following :

+ start-v : V
+ random-generator: (no args) -> V
+ new-v-generator: V, V -> V ; nearest, random -> actual
+ edge-prohibited-p: V, V -> bool ; nearest, new -> result
+ finish-p: V -> bool ; new -> result
+ run-on-node: V, V -> t ; nearest, new ->

Package

cl-rrt

Source

rrt.lisp (file)

Function: split-branch-rrt-search RANDOM-GENERATOR NEW-VS-GENERATOR &key EDGE-PROHIBITED-P FINISH-P START-V TREE TREE-CLASS TREE-CLASS-OPTIONS MAX-NODES MAX-ITERATION RUN-ON-NODE

RRT-search function with split edges.

Package

cl-rrt

Source

rrt.lisp (file)

6.1.2 Generic functions

Generic Function: children OBJECT

Generic Function: (setf children) NEW-VALUE OBJECT

Package

cl-rrt

Methods

Method: children (RRT-TREE-NODE rrt-tree-node)

automatically generated reader method

Source

rrt.lisp (file)

Method: (setf children) NEW-VALUE (RRT-TREE-NODE rrt-tree-node)

automatically generated writer method

Source

rrt.lisp (file)

Generic Function: configuration-space-distance POINT1 POINT2

V, V -> NUMBER
This generic function should provide a method
to measure the distance between two points in C-space (configuration space).

Package

cl-rrt

Source

rrt.lisp (file)

Generic Function: content OBJECT

Generic Function: (setf content) NEW-VALUE OBJECT

Package

cl-rrt

Methods

Method: content (RRT-TREE-NODE rrt-tree-node)

automatically generated reader method

Source

rrt.lisp (file)

Method: (setf content) NEW-VALUE (RRT-TREE-NODE rrt-tree-node)

automatically generated writer method

Source

rrt.lisp (file)

Generic Function: count-nodes TREE

TREE -> FIXNUM
This generic function should provide a method to count the number of leafs.

Package

cl-rrt

Source

rrt.lisp (file)

Methods

Method: count-nodes (TREE rrt-tree-tree)

Source

rrt-tree-tree.lisp (file)

Method: count-nodes (TREE rrt-tree-mixin)

Generic Function: finish-node OBJECT

Generic Function: (setf finish-node) NEW-VALUE OBJECT

Package

cl-rrt

Methods

Method: finish-node (RRT-TREE-MIXIN rrt-tree-mixin)

Method: (setf finish-node) NEW-VALUE (RRT-TREE-MIXIN rrt-tree-mixin)

Source

rrt.lisp (file)

Generic Function: insert CONTENT TREE

V, TREE -> TREE
This generic function is allowed provide
an additional procedure during the insertion of a ‘content’ to the ‘tree’. The code in this method does something other than the linking of the parent and child nodes, and optimizes nearest-search. For example,
if you want to use B-tree for the nearest search,
here you can add codes for inserting a content into a B-tree.
Always returns ‘tree’ as a result of :around method of rrt-tree-mixin.

Package

cl-rrt

Source

rrt.lisp (file)

Methods

Method: insert (NODE rrt-tree-node) (TREE rrt-tree-list)

Source

rrt-tree-list.lisp (file)

Method: insert (V rrt-tree-node) (TREE rrt-tree-mixin)

Method: insert (V rrt-tree-node) (TREE rrt-tree-mixin) around

Generic Function: leafs TREE

TREE -> (list (node V))
This generic function should provide a method to accumulate all leafs into a list.
A leaf is a node with no children.

Package

cl-rrt

Source

rrt.lisp (file)

Methods

Method: leafs (TREE rrt-tree-tree)

Source

rrt-tree-tree.lisp (file)

Method: leafs (TREE rrt-tree-mixin)

Generic Function: nearest-node TARGET TREE

V, tree -> (node V), NUMBER, V

This generic function should implement a method
which finds the nearest node in a ‘tree’ to the ‘target’. It returns multiple-values.

1. The first return value should be the nearest node.
2. The second value should be the distance between the target and the nearest node.
3. The third value should be the content of the node.

Package

cl-rrt

Source

rrt.lisp (file)

Methods

Method: nearest-node TARGET-CONTENT (TREE rrt-tree-tree)

Source

rrt-tree-tree.lisp (file)

Method: nearest-node TARGET-CONTENT (TREE rrt-tree-list)

Source

rrt-tree-list.lisp (file)

Generic Function: nodes OBJECT

Generic Function: (setf nodes) NEW-VALUE OBJECT

Package

cl-rrt

Methods

Method: nodes (TREE rrt-tree-tree)

Source

rrt-tree-tree.lisp (file)

Method: nodes (RRT-TREE-LIST rrt-tree-list)

automatically generated reader method

Source

rrt-tree-list.lisp (file)

Method: (setf nodes) NEW-VALUE (RRT-TREE-LIST rrt-tree-list)

automatically generated writer method

Source

rrt-tree-list.lisp (file)

Generic Function: parent OBJECT

Generic Function: (setf parent) NEW-VALUE OBJECT

Package

cl-rrt

Methods

Method: parent (RRT-TREE-NODE rrt-tree-node)

automatically generated reader method

Source

rrt.lisp (file)

Method: (setf parent) NEW-VALUE (RRT-TREE-NODE rrt-tree-node)

automatically generated writer method

Source

rrt.lisp (file)

Generic Function: root OBJECT

Generic Function: (setf root) NEW-VALUE OBJECT

Package

cl-rrt

Methods

Method: root (RRT-TREE-MIXIN rrt-tree-mixin)

automatically generated reader method

Source

rrt.lisp (file)

Method: (setf root) NEW-VALUE (RRT-TREE-MIXIN rrt-tree-mixin)

automatically generated writer method

Source

rrt.lisp (file)

6.1.3 Conditions

Condition: child-not-found ()

Package

cl-rrt

Source

rrt.lisp (file)

Direct superclasses

simple-condition (condition)

Direct slots

Slot: parent

Slot: child

6.1.4 Classes

Class: rrt-tree-list ()

an rrt-tree implementation which uses
a simple linear search method for nearest-search.

Package

cl-rrt

Source

rrt-tree-list.lisp (file)

Direct superclasses

rrt-tree-mixin (class)

Direct methods

• insert (method)
• nearest-node (method)
• reinitialize-instance (method)
• print-object (method)
• nodes (method)
• nodes (method)

Direct slots

Slot: nodes

Type

list

Readers

nodes (generic function)

Writers

(setf nodes) (generic function)

Class: rrt-tree-mixin ()

The abstract interface mixin class of rrt-tree. User do not create
an instance of it, but rather inherit it. It has three slots and accessors with the same names:

+ root : the root node of the tree. of type rrt-tree-node.
+ finish : a slot which contains the last node of the computed path.
It is bound to nil, it means the previous search has failed to find
a path which satisfies the goal condition.

Package

cl-rrt

Source

rrt.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• rrt-tree-list (class)
• rrt-tree-tree (class)

Direct methods

• count-nodes (method)
• leafs (method)
• insert (method)
• insert (method)
• initialize-instance (method)
• finish-node (method)
• finish-node (method)
• root (method)
• root (method)

Direct slots

Slot: root

Type

(or null cl-rrt:rrt-tree-node)

Initargs

:root

Readers

root (generic function)

Writers

(setf root) (generic function)

Slot: finish-node

Type

(or null cl-rrt:rrt-tree-node)

Initargs

:finish-node

Readers

finish-node (generic function)

Writers

(setf finish-node) (generic function)

Class: rrt-tree-node ()

Node class of Random Tree.

Package

cl-rrt

Source

rrt.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• insert (method)
• insert (method)
• insert (method)
• content (method)
• content (method)
• children (method)
• children (method)
• parent (method)
• parent (method)

Direct slots

Slot: parent

Type

(or null cl-rrt:rrt-tree-node)

Initargs

:parent

Readers

parent (generic function)

Writers

(setf parent) (generic function)

Slot: children

Type

list

Readers

children (generic function)

Writers

(setf children) (generic function)

Slot: content

Initargs

:content

Readers

content (generic function)

Writers

(setf content) (generic function)

Class: rrt-tree-tree ()

an rrt-tree implementation which seaches from the root in nearest-search.

Package

cl-rrt

Source

rrt-tree-tree.lisp (file)

Direct superclasses

rrt-tree-mixin (class)

Direct methods

• count-nodes (method)
• leafs (method)
• nodes (method)
• nearest-node (method)
• reinitialize-instance (method)
• print-object (method)

6.2 Internal definitions

6.2.1 Functions

Function: %nearest-node-list TARGET-CONTENT LST

Package

cl-rrt

Source

rrt-tree-list.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types