The cl-rrt Reference Manual

This is the cl-rrt Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Sep 15 04:24:19 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

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


2.1 cl-rrt

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

Author

Masataro Asai

Contact

License

LLGPL

Version

0.1

Dependencies
  • iterate (system).
  • alexandria (system).
  • cl-syntax-annot (system).
  • anaphora (system).
Source

cl-rrt.asd.

Child Component

src (module).


3 Modules

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


3.1 cl-rrt/src

Source

cl-rrt.asd.

Parent Component

cl-rrt (system).

Child Components

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/cl-rrt.asd

Source

cl-rrt.asd.

Parent Component

cl-rrt (system).

ASDF Systems

cl-rrt.


4.1.2 cl-rrt/src/package.lisp

Source

cl-rrt.asd.

Parent Component

src (module).

Packages

cl-rrt.


4.1.3 cl-rrt/src/rrt.lisp

Dependency

package.lisp (file).

Source

cl-rrt.asd.

Parent Component

src (module).

Public Interface

4.1.4 cl-rrt/src/helper.lisp

Dependency

rrt.lisp (file).

Source

cl-rrt.asd.

Parent Component

src (module).

Public Interface

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

Dependency

helper.lisp (file).

Source

cl-rrt.asd.

Parent Component

src (module).

Public Interface
Internals

%nearest-node-list (function).


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

Dependency

rrt-tree-list.lisp (file).

Source

cl-rrt.asd.

Parent Component

src (module).

Public Interface

5 Packages

Packages are listed by definition order.


5.1 cl-rrt

Source

package.lisp.

Nickname

rrt

Use List
  • alexandria.
  • anaphora.
  • cl-annot.
  • cl-annot.class.
  • cl-annot.doc.
  • cl-annot.slot.
  • cl-syntax.
  • common-lisp.
  • iterate.
Public Interface
Internals

%nearest-node-list (function).


6 Definitions

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


6.1 Public Interface


6.1.1 Ordinary 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.

Function: connect (parent child)

connect two nodes as a parent and a child.

Package

cl-rrt.

Source

rrt.lisp.

Function: disconnect (parent child)

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

Package

cl-rrt.

Source

rrt.lisp.

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.

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.

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.

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.

Function: neglect (parent)

HELPER FUNCTION: disconnect all children from the specified parent

Package

cl-rrt.

Source

helper.lisp.

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.

Function: orphanize (child)

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

Package

cl-rrt.

Source

helper.lisp.

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.

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.

Function: rrt-node (content)

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

Package

cl-rrt.

Source

rrt.lisp.

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.

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.


6.1.2 Generic functions

Generic Reader: children (object)
Package

cl-rrt.

Methods
Reader Method: children ((rrt-tree-node rrt-tree-node))

automatically generated reader method

Source

rrt.lisp.

Target Slot

children.

Generic Writer: (setf children) (object)
Package

cl-rrt.

Methods
Writer Method: (setf children) ((rrt-tree-node rrt-tree-node))

automatically generated writer method

Source

rrt.lisp.

Target Slot

children.

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.

Generic Reader: content (object)
Package

cl-rrt.

Methods
Reader Method: content ((rrt-tree-node rrt-tree-node))

automatically generated reader method

Source

rrt.lisp.

Target Slot

content.

Generic Writer: (setf content) (object)
Package

cl-rrt.

Methods
Writer Method: (setf content) ((rrt-tree-node rrt-tree-node))

automatically generated writer method

Source

rrt.lisp.

Target Slot

content.

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.

Methods
Method: count-nodes ((tree rrt-tree-tree))
Source

rrt-tree-tree.lisp.

Method: count-nodes ((tree rrt-tree-mixin))
Generic Reader: finish-node (object)
Generic Writer: (setf finish-node) (object)
Package

cl-rrt.

Methods
Reader Method: finish-node ((rrt-tree-mixin rrt-tree-mixin))
Writer Method: (setf finish-node) ((rrt-tree-mixin rrt-tree-mixin))
Source

rrt.lisp.

Target Slot

finish-node.

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.

Methods
Method: insert ((node rrt-tree-node) (tree rrt-tree-list))
Source

rrt-tree-list.lisp.

Method: insert ((v rrt-tree-node) (tree rrt-tree-mixin))
Method: insert :around ((v rrt-tree-node) (tree rrt-tree-mixin))
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.

Methods
Method: leafs ((tree rrt-tree-tree))
Source

rrt-tree-tree.lisp.

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.

Methods
Method: nearest-node (target-content (tree rrt-tree-tree))
Source

rrt-tree-tree.lisp.

Method: nearest-node (target-content (tree rrt-tree-list))
Source

rrt-tree-list.lisp.

Generic Function: nodes (object)
Package

cl-rrt.

Methods
Method: nodes ((tree rrt-tree-tree))
Source

rrt-tree-tree.lisp.

Reader Method: nodes ((rrt-tree-list rrt-tree-list))

automatically generated reader method

Source

rrt-tree-list.lisp.

Target Slot

nodes.

Generic Writer: (setf nodes) (object)
Package

cl-rrt.

Methods
Writer Method: (setf nodes) ((rrt-tree-list rrt-tree-list))

automatically generated writer method

Source

rrt-tree-list.lisp.

Target Slot

nodes.

Generic Reader: parent (object)
Package

cl-rrt.

Methods
Reader Method: parent ((rrt-tree-node rrt-tree-node))

automatically generated reader method

Source

rrt.lisp.

Target Slot

parent.

Generic Writer: (setf parent) (object)
Package

cl-rrt.

Methods
Writer Method: (setf parent) ((rrt-tree-node rrt-tree-node))

automatically generated writer method

Source

rrt.lisp.

Target Slot

parent.

Generic Reader: root (object)
Package

cl-rrt.

Methods
Reader Method: root ((rrt-tree-mixin rrt-tree-mixin))

automatically generated reader method

Source

rrt.lisp.

Target Slot

root.

Generic Writer: (setf root) (object)
Package

cl-rrt.

Methods
Writer Method: (setf root) ((rrt-tree-mixin rrt-tree-mixin))

automatically generated writer method

Source

rrt.lisp.

Target Slot

root.


6.1.3 Standalone methods

Method: initialize-instance :after ((tree rrt-tree-mixin) &rest args &key root &allow-other-keys)
Source

rrt.lisp.

Method: print-object ((tree rrt-tree-tree) s)
Source

rrt-tree-tree.lisp.

Method: print-object ((tree rrt-tree-list) s)
Source

rrt-tree-list.lisp.

Method: reinitialize-instance :around ((tree rrt-tree-tree) &rest args)
Source

rrt-tree-tree.lisp.

Method: reinitialize-instance :around ((tree rrt-tree-list) &rest args)
Source

rrt-tree-list.lisp.


6.1.4 Conditions

Condition: child-not-found
Package

cl-rrt.

Source

rrt.lisp.

Direct superclasses

simple-condition.

Direct slots
Slot: parent
Slot: child

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

Direct superclasses

rrt-tree-mixin.

Direct methods
Direct slots
Slot: nodes
Type

list

Readers

nodes.

Writers

(setf nodes).

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.

Direct subclasses
Direct methods
Direct slots
Slot: root
Type

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

Initargs

:root

Readers

root.

Writers

(setf root).

Slot: finish-node
Type

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

Initargs

:finish-node

Readers

finish-node.

Writers

(setf finish-node).

Class: rrt-tree-node

Node class of Random Tree.

Package

cl-rrt.

Source

rrt.lisp.

Direct methods
Direct slots
Slot: parent
Type

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

Initargs

:parent

Readers

parent.

Writers

(setf parent).

Slot: children
Type

list

Readers

children.

Writers

(setf children).

Slot: content
Initargs

:content

Readers

content.

Writers

(setf content).

Class: rrt-tree-tree

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

Package

cl-rrt.

Source

rrt-tree-tree.lisp.

Direct superclasses

rrt-tree-mixin.

Direct methods

6.2 Internals


6.2.1 Ordinary functions

Function: %nearest-node-list (target-content lst)
Package

cl-rrt.

Source

rrt-tree-list.lisp.


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
A   C   D   F   G   I   L   M   N   O   P   R   S  
Index Entry  Section

%
%nearest-node-list: Private ordinary functions

(
(setf children): Public generic functions
(setf children): Public generic functions
(setf content): Public generic functions
(setf content): Public generic functions
(setf finish-node): Public generic functions
(setf finish-node): Public generic functions
(setf nodes): Public generic functions
(setf nodes): Public generic functions
(setf parent): Public generic functions
(setf parent): Public generic functions
(setf root): Public generic functions
(setf root): Public generic functions

A
adopt-children: Public ordinary functions

C
children: Public generic functions
children: Public generic functions
configuration-space-distance: Public generic functions
connect: Public ordinary functions
content: Public generic functions
content: Public generic functions
count-nodes: Public generic functions
count-nodes: Public generic functions
count-nodes: Public generic functions

D
disconnect: Public ordinary functions

F
finish-node: Public generic functions
finish-node: Public generic functions
Function, %nearest-node-list: Private ordinary functions
Function, adopt-children: Public ordinary functions
Function, connect: Public ordinary functions
Function, disconnect: Public ordinary functions
Function, map-rrt-tree-content-recursively: Public ordinary functions
Function, map-rrt-tree-node-recursively: Public ordinary functions
Function, mapc-rrt-tree-content-recursively: Public ordinary functions
Function, mapc-rrt-tree-node-recursively: Public ordinary functions
Function, neglect: Public ordinary functions
Function, nnext-branch: Public ordinary functions
Function, orphanize: Public ordinary functions
Function, result-path: Public ordinary functions
Function, result-path-nodes: Public ordinary functions
Function, rrt-node: Public ordinary functions
Function, rrt-search: Public ordinary functions
Function, split-branch-rrt-search: Public ordinary functions

G
Generic Function, (setf children): Public generic functions
Generic Function, (setf content): Public generic functions
Generic Function, (setf finish-node): Public generic functions
Generic Function, (setf nodes): Public generic functions
Generic Function, (setf parent): Public generic functions
Generic Function, (setf root): Public generic functions
Generic Function, children: Public generic functions
Generic Function, configuration-space-distance: Public generic functions
Generic Function, content: Public generic functions
Generic Function, count-nodes: Public generic functions
Generic Function, finish-node: Public generic functions
Generic Function, insert: Public generic functions
Generic Function, leafs: Public generic functions
Generic Function, nearest-node: Public generic functions
Generic Function, nodes: Public generic functions
Generic Function, parent: Public generic functions
Generic Function, root: Public generic functions

I
initialize-instance: Public standalone methods
insert: Public generic functions
insert: Public generic functions
insert: Public generic functions
insert: Public generic functions

L
leafs: Public generic functions
leafs: Public generic functions
leafs: Public generic functions

M
map-rrt-tree-content-recursively: Public ordinary functions
map-rrt-tree-node-recursively: Public ordinary functions
mapc-rrt-tree-content-recursively: Public ordinary functions
mapc-rrt-tree-node-recursively: Public ordinary functions
Method, (setf children): Public generic functions
Method, (setf content): Public generic functions
Method, (setf finish-node): Public generic functions
Method, (setf nodes): Public generic functions
Method, (setf parent): Public generic functions
Method, (setf root): Public generic functions
Method, children: Public generic functions
Method, content: Public generic functions
Method, count-nodes: Public generic functions
Method, count-nodes: Public generic functions
Method, finish-node: Public generic functions
Method, initialize-instance: Public standalone methods
Method, insert: Public generic functions
Method, insert: Public generic functions
Method, insert: Public generic functions
Method, leafs: Public generic functions
Method, leafs: Public generic functions
Method, nearest-node: Public generic functions
Method, nearest-node: Public generic functions
Method, nodes: Public generic functions
Method, nodes: Public generic functions
Method, parent: Public generic functions
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, reinitialize-instance: Public standalone methods
Method, reinitialize-instance: Public standalone methods
Method, root: Public generic functions

N
nearest-node: Public generic functions
nearest-node: Public generic functions
nearest-node: Public generic functions
neglect: Public ordinary functions
nnext-branch: Public ordinary functions
nodes: Public generic functions
nodes: Public generic functions
nodes: Public generic functions

O
orphanize: Public ordinary functions

P
parent: Public generic functions
parent: Public generic functions
print-object: Public standalone methods
print-object: Public standalone methods

R
reinitialize-instance: Public standalone methods
reinitialize-instance: Public standalone methods
result-path: Public ordinary functions
result-path-nodes: Public ordinary functions
root: Public generic functions
root: Public generic functions
rrt-node: Public ordinary functions
rrt-search: Public ordinary functions

S
split-branch-rrt-search: Public ordinary functions