The Cuik KD-Tree Library


The Cuik-KDtree Documentation

Introduction

This package is an implementation of a kd-tree specially aimed for path planning.

This library is a replacement for the MPNN library by Anna Yershova and Steven M. LaValle, but:

  • MPNN is designed to solve k-nearest neighbour queries (including the case k=1). We focus on the nearest-neighbour query since it is the only one necesary to build a RRT.
  • We extended the MPNN library to solve the search for neighbours in a ball (this operation is necessary in modern motion planning algorithms like RRT*). This extension, though, is probably not as efficient as it could be. The cuik-kdtree library is directly designed to determine the neighbours in a ball.
  • MPNN can handle three types of topologies (R,S,RP). The cuik-kdtree only handels two topologies (R and S).
  • The cuik-kdtree library is directly implemented in C (like the CuikSuite) and, thus, it does not require of a C++ to C interface, which slows down the use of MPNN from the CuikSuite.
  • The MPNN library can not be easily adapted to used it for sampling. The cuik-kdtree library allows using the kd-tree for sampling using the idea of:
    • A. Yershova and S. M. Lavalle, Motion Planning for Highly Constrained Spaces, 2009.
    • J. Bialkowski, M. Otte, E. Frazzoli, Free-configuration Biased Sampling for Motion Planning, 2013.

License

The library has been developed by the KRD group at IRI and is licensed under GPLv3 License.

Download

You can download the sources from here.


Compilation

Unpack the package and move to the build folder

  • tar xzf cuik-kdtree.tar.gz
  • cd Cuik-KDtree/build

Generate the makefiles

  • cmake ..

Compile the package

  • make

At this point the library is available localy in lib folder and a minimalistic test-cuik-kdtree program is available in the bin folder. This test-cuik-kdtree program can be used as:

Execute

to get help on the parameters of this test program.

This test program compares the cuik-kdtree to a brute force approach and to the MPNN. Actually you will need the extended version of this library.

To install the library into the system folders execute

  • make install

The default installation folder is /usr/local. This can be changed by setting the environment variable CMAKE_INSTALL_PREFIX.

The documentation for the library can be generated executing

  • make doc

in the build directory. The documentation can be browsed from the file doc/html/index.html.