Common Lisp Package: CL-RRT

README:

FUNCTION

Public

ADOPT-CHILDREN (NEW-PARENT OLD-PARENT)

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

CONNECT (PARENT CHILD)

connect two nodes as a parent and a child.

DISCONNECT (PARENT CHILD)

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

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.

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.

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.

MAPC-RRT-TREE-NODE-RECURSIVELY (NODE FN)

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

NEGLECT (PARENT)

HELPER FUNCTION: disconnect all children from the specified parent

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.

ORPHANIZE (CHILD)

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

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.

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.

RRT-NODE (CONTENT)

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

Private

Undocumented

%NEAREST-NODE-LIST (TARGET-CONTENT LST)

GENERIC-FUNCTION

Public

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

COUNT-NODES (TREE)

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

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.

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.

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.

SLOT-ACCESSOR

Public

FINISH-NODE (OBJECT)

SETFFINISH-NODE (NEW-VALUE OBJECT)

Undocumented

CHILDREN (OBJECT)

SETFCHILDREN (NEW-VALUE OBJECT)

CONTENT (OBJECT)

SETFCONTENT (NEW-VALUE OBJECT)

NODES (OBJECT)

SETFNODES (NEW-VALUE OBJECT)

PARENT (OBJECT)

SETFPARENT (NEW-VALUE OBJECT)

ROOT (OBJECT)

SETFROOT (NEW-VALUE OBJECT)

CLASS

Public

RRT-TREE-LIST

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

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.

RRT-TREE-NODE

Node class of Random Tree.

RRT-TREE-TREE

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

CONDITION

Public

CHILD-NOT-FOUND