gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609
cmake version 3.5.2
ninja version 0.1.3
The Compile message is...

mkdir -p build
cd build && cmake .. -DCMAKE_INSTALL_PREFIX:PATH="" -GNinja && ninja
-- Found Qt5: /usr/lib/x86_64-linux-gnu/cmake/Qt5Widgets
CMake Error at /usr/share/cmake-3.5/Modules/ExternalProject.cmake:964 (message):
error: do not know how to extract
'/home/travis-byun/WorkSpace_vim/rrt/rrt-master/third_party/googletest/googletest'
-- known types are .7z, .tar, .tar.bz2, .tar.gz, .tar.xz, .tbz2, .tgz, .txz
and .zip
Call Stack (most recent call first):
/usr/share/cmake-3.5/Modules/ExternalProject.cmake:1909 (_ep_write_extractfile_script)
/usr/share/cmake-3.5/Modules/ExternalProject.cmake:2459 (_ep_add_download_command)
cmake/SetupGTest.cmake:5 (ExternalProject_Add)
CMakeLists.txt:96 (include)

-- Configuring incomplete, errors occurred!
See also "/home/travis-byun/WorkSpace_vim/rrt/rrt-master/build/CMakeFiles/CMakeOutput.log".
makefile:2: recipe for target 'all' failed
make: *** [all] Error 1

This makes it easier to compare performance between different approaches such as @joshhting's dynamic step size code in issue #13.

In the gridSquareForLocation function of class ObstacleGrid here:
original code

Shouldn't the result be the following?

    return Vector2i(loc.x() / discretizedWidth(),
                    loc.y() / discretizedHeight());

As I understand the code, width and height refers to the size of the whole space. discretizedWidth and discretizedHeight refers to the size of the grids. Correct me if I am wrong. Thank you!

We're pushing and popping, might as well use a stack

Right now it returns the first path it finds, but sometimes it's best to continue running a bit longer to find a better path. This would require modifying RRT::Tree.run().

Because there tends to be very few obstacles during a match, we could benefit by implementing an algorithm that is not necessarily robust with dealing with obstacles but rather very efficient when it can find a solution. One of these algorithms is Straight Path Planning. It begins by drawing a straight line between the robot and the goal. While there are obstacles within that path, it will tweak the path a bit until it can avoid all obstacles. If Straight Path Planning is not able to find a solution, we will fall back to RRT.

Bezier curves should not go through obstacles

Preferably with Doxygen

For academic approach, Can you explain more details about what the theory you adopted in your code?

like:
Path Generation: Batch informed trees(BIT*).
Path smoothing: Single Polar Polynomial(SPP) curve or Clothoid curve.
some others:

Thank for your help.

I think the hard-set qt directory prevents cross-platform builds. Possibly look into CMake instead of scons.

Path should not go through obstacle corners

Right now tree growth is totally random. A much better implementation would be to extend towards a random point with probability p and extend towards the goal with probability 1-p.

As far as I can tell, things are setup correctly and I have the docker auth variables set in the circleci environment. The build logs show that the image was pushed to the repo, but the docker hub page shows otherwise.

See this build and the docker hub page.

Right now goal bias is just a percentage chance that we go directly towards the goal, it should be modified to be changing the probability function itself, so that we don't just go towards the goal when we do choose to do so (but we have a higher probability of going some direction closer to the goal). This will help us go around obstacles better while still having a high goal bias.

Suggested by @barulicm

The screenshot on the rrt page is outdated. We now have bezier curves and an improved interface and stuff.

http://en.wikipedia.org/wiki/K-d_tree

Here's a picture of what I've got now. It needs some work, but it's looking pretty decent.

Right now the RRT has much less documentation than I'd like (the RRT is one of the most useful parts of our codebase, since it's modularized). We need to try to make thorough docs for the rrt.

Once we have most of the way done to this, I'll add documentation generation so we can have a RRT docs site we can link to on our README, just like robocup-software and robocup-firmware.

This is a good beginner issue, especially for new members interested in path planning, if you were ok with just reading some code.

See #55 and #48.

• Document why we use Dequeue instead of a vector.
• Document hotkeys, e.x., those listed in #58

#36 is a subissue of this issue.

I'm interested in using this code to run my robot, which uses windows, unfortunately :( . How easy would this be, and do you have any suggestions? Are there any particular C++ version dependencies?

I get this error while I try to 'make'

CMake Error at /usr/share/cmake-2.8/Modules/ExternalProject.cmake:609 (message):
error: do not know how to extract
'/home/boon/Packages/RoboJackets_RRT/rrt/third_party/googletest/googletest'
-- known types are .bz2, .tar, .tar.gz, .tgz and .zip
Call Stack (most recent call first):
/usr/share/cmake-2.8/Modules/ExternalProject.cmake:1420 (_ep_write_extractfile_script)
/usr/share/cmake-2.8/Modules/ExternalProject.cmake:1805 (_ep_add_download_command)
cmake/SetupGTest.cmake:4 (ExternalProject_Add)
CMakeLists.txt:75 (include)
-- Configuring incomplete, errors occurred!
See also "/home/boon/Packages/RoboJackets_RRT/rrt/build/CMakeFiles/CMakeOutput.log".
make: *** [all] Error 1

Step size is something we need to tune a bit to our application, so it would be nice to have an option for it in the gui.

The refined path right now is a minimil set of waypoints build from the actual RRT path. We remove any waypoints that are unnecessary (most of them) for the path to be collision-free. This results in a decent path, but it's still a series of line segments, which is obviously not a good motion path. The next step is to apply a curve overtop of this so that is smooth and doesn't have any corners. There are a few ways to do this although I haven't figured out the best yet.

One neat solution I saw was to use some heuristics to generate a first attempt at a bezier interpolation, then to optimize the bezier parameters to get closer to the fastest-travellable path.

Here's a good paper I found on this - it's a long read, but skimming it gave some good info: http://www2.informatik.uni-freiburg.de/~lau/students/Sprunk2008.pdf.

This will be based on the ideas presented here: http://msl.cs.uiuc.edu/~lavalle/papers/LavKuf01b.pdf

Dragging the mouse around before the first click is made causes obstacles to be added.

After the first click, everything is fine.

This can be solved by adding _editingObstacles = false; to this file in the constructor

This would allow us to run the rrt a bunch of times and collect the iteration counts for each one in one place, which could be useful for comparing the efficiency of a new implementation to that of an old one.

We should implement ERRTs as described in this CMU Paper. The main difference is the use of the "waypoint cache". After a successful path plan, we save a fixed-length subset of the waypoints in a cache. The next path-planning iteration grows a new tree, but it is biased towards the previously-saved waypoints.

Hi,

I am running Ubuntu 14.0.4 and as I run make in the main folder, I get the following error:

CMake Error at CMakeLists.txt:71 (get_filename_component): get_filename_component unknown component DIRECTORY

Kindly guide me what could be the problem here.

Thanks,
Umer

In the destructor of the Tree class, seems that a parameter should be passed to avoid memory leak:

    virtual ~Tree() { reset(true); }

This is useful for robot planning if we start out in a virtual obstacle where we're not supposed to be. The current implementation will fail to find us a path out of the obstacle.

This will make it easier for visualizing the RRT's use in RoboCup. Their size vs the plane size should be the same proportion as robocup robots to the field size.

This allows us to exactly reproduce rrt runs, which is useful for test reproducability.