Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
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.
• Introduction | What cl-rrt is all about | |
• Systems | The systems documentation | |
• Modules | The modules documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
#+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.
Next: Modules, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The cl-rrt system |
Masataro Asai
LLGPL
Common Lisp implementation of RRT (Rapidily exploring Random Tree), a fast probabilistic multidimentional path-plannning algorithm.
0.1
cl-rrt.asd (file)
src (module)
Modules are listed depth-first from the system components tree.
• The cl-rrt/src module |
cl-rrt (system)
src/
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files |
Next: The cl-rrt/src/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
cl-rrt.asd
cl-rrt (system)
Next: The cl-rrt/src/rrt․lisp file, Previous: The cl-rrt․asd file, Up: Lisp files [Contents][Index]
Next: The cl-rrt/src/helper․lisp file, Previous: The cl-rrt/src/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
src (module)
src/rrt.lisp
Next: The cl-rrt/src/rrt-tree-list․lisp file, Previous: The cl-rrt/src/rrt․lisp file, Up: Lisp files [Contents][Index]
rrt.lisp (file)
src (module)
src/helper.lisp
Next: The cl-rrt/src/rrt-tree-tree․lisp file, Previous: The cl-rrt/src/helper․lisp file, Up: Lisp files [Contents][Index]
helper.lisp (file)
src (module)
src/rrt-tree-list.lisp
%nearest-node-list (function)
Previous: The cl-rrt/src/rrt-tree-list․lisp file, Up: Lisp files [Contents][Index]
rrt-tree-list.lisp (file)
src (module)
src/rrt-tree-tree.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The cl-rrt package |
package.lisp (file)
rrt
%nearest-node-list (function)
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported functions | ||
• Exported generic functions | ||
• Exported conditions | ||
• Exported classes |
Next: Exported generic functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
HELPER FUINCTION: removes the children of old-parent and the new-parent takes all of them.
helper.lisp (file)
connect two nodes as a parent and a child.
disconnect a parent and its child. signals CHILD-NOT-FOUND < SIMPLE-CONDITION.
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 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 over the contents of RRT-TREE-NODEs ofthe tree and returns nil. Only for the side effect.
Mapc over the RRT-TREE-NODEs of the tree and returns nil. Only for the side effect.
HELPER FUNCTION: disconnect all children from the specified parent
helper.lisp (file)
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.
HELPER FUNCTION: ensure a node doesn’t have a parent
helper.lisp (file)
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.
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.
Identical to =(make-instance ’rrt-tree-node :content content)=
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 ->
RRT-search function with split edges.
Next: Exported conditions, Previous: Exported functions, Up: Exported definitions [Contents][Index]
V, V -> NUMBER
This generic function should provide a method
to measure the distance between two points in C-space
(configuration space).
TREE -> FIXNUM
This generic function should provide a method
to count the number of leafs.
rrt.lisp (file)
rrt-tree-tree.lisp (file)
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.
rrt.lisp (file)
rrt-tree-list.lisp (file)
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.
rrt.lisp (file)
rrt-tree-tree.lisp (file)
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.
rrt.lisp (file)
rrt-tree-tree.lisp (file)
rrt-tree-list.lisp (file)
rrt-tree-tree.lisp (file)
automatically generated reader method
rrt-tree-list.lisp (file)
automatically generated writer method
rrt-tree-list.lisp (file)
Next: Exported classes, Previous: Exported generic functions, Up: Exported definitions [Contents][Index]
Previous: Exported conditions, Up: Exported definitions [Contents][Index]
an rrt-tree implementation which uses
a simple linear search method for nearest-search.
rrt-tree-list.lisp (file)
rrt-tree-mixin (class)
list
nodes (generic function)
(setf nodes) (generic function)
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.lisp (file)
standard-object (class)
(or null cl-rrt:rrt-tree-node)
:root
root (generic function)
(setf root) (generic function)
(or null cl-rrt:rrt-tree-node)
:finish-node
finish-node (generic function)
(setf finish-node) (generic function)
Node class of Random Tree.
rrt.lisp (file)
standard-object (class)
(or null cl-rrt:rrt-tree-node)
:parent
parent (generic function)
(setf parent) (generic function)
list
children (generic function)
(setf children) (generic function)
:content
content (generic function)
(setf content) (generic function)
an rrt-tree implementation which seaches from the root in nearest-search.
rrt-tree-tree.lisp (file)
rrt-tree-mixin (class)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal functions |
Previous: Internal definitions, Up: Internal definitions [Contents][Index]
rrt-tree-list.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | C F L M |
---|
Jump to: | C F L M |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
Jump to: | %
(
A C D F G I L M N O P R S |
---|
Jump to: | %
(
A C D F G I L M N O P R S |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
Jump to: | C F N P R S |
---|
Jump to: | C F N P R S |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | C P R S |
---|
Jump to: | C P R S |
---|