Improved path planner - Githubissues

justbuchanan commented 10 years ago

Our path planner currently doesn't take into account robot velocity. Doing so could greatly improve our results.
We need a way to specify a target location in terms of time. Currently, the path planner can be told to get a robot to a specific point. This works well for moving to a particular area and staying there, but isn't as well suited for things like capturing a moving ball which happens often throughout the game.

Things to consider:

robot initial and final velocity
how are path constraints specified?
incremental planning - we don't necessarily need to recalculate the whole path every iteration
priority - the robot with the ball should be planned first
moving vs static obstacles

We currently use RRTs for our planning: http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree

Also, here are a couple other good readings: http://users.soe.ucsc.edu/~elkaim/Documents/Choi_AIAA_GNC10_RealTime.pdf http://linawolf.de/fileadmin/user_upload/papers/pathplanning-ourima.pdf

justbuchanan commented 10 years ago

I've started doing some work on this on the justin/motioncontrol branch.

justbuchanan commented 10 years ago

Also, check out the rrt repo where I've started putting new rrt code and an interactive viewer/demo.

justbuchanan commented 10 years ago

This is a great paper on RRTs that incorporate dynamics: http://robotics.stanford.edu/~latombe/cs326/2007/class13/LavKuf.pdf

justbuchanan commented 10 years ago

Here's another good paper: http://www.cs.cmu.edu/~mmv/papers/02iros-rrt.pdf

justbuchanan commented 9 years ago

Here's the paper for the straight-line idea we saw at the symposium this year: http://fei.edu.br/rcs/2014/RegularPapers/robocupsymposium2014_submission_55.pdf

joshhting commented 9 years ago

What happened to justin/motioncontrol? Is it still up on GitHub?

justbuchanan commented 9 years ago

I think I deleted that a while ago as I made more progress on the rrt applet. That branch just had a little bit different implementation of the RRT data structure / algorithm which ended up just being used in the applet.

It might be best to work with the applet and experiment with some different things. Probably the most important thing during the dev phase of a new path planner is being able to visualize what's going on. Right now the rrt applet does that pretty well, although some of that could be ported back to soccer.

One thing that might be nice to look at is biasing rrt growth in the direction of the target point. Also, I'd look into Extended RRTs. That being said, we don't have to use anything based on RRTs - I know some teams use some version of A-Star and there are a few other options available too.

justbuchanan commented 9 years ago

One of our main problems now is that paths planned for a robot aren't consistent. If there's an obstacle in a robot's way, the planner will plan a path around it. The next time the path is replanned (typically the next frame), it will plan another path around it. Often times, these subsequently-planned paths are significantly different, which leads to poor performance. It's really hard to follow a path if it's constantly moving by a large amount. It would be nice if paths changed as little as possible from frame to frame so the robot can do a much better job of following it.

One approach to generating similar paths iteration after iteration is by using Extended RRTs (ERRTs). The main idea is that you bias the new RRT to grow towards the previous path. That way the result is likely to be very similar. Check out CMU's paper on ERRTs here: http://www.cs.cmu.edu/~15780/readings/02iros-errt.pdf.

justbuchanan commented 9 years ago

I added a few issues to the tracker on the rrt repo with some ideas on how to improve it.

Probably the best way to go about improving path planning would be to add the enhancements to the rrt applet, then modify the soccer program to use that as an external library. That way it will be easy to visualize what's going on during and after development and it will keep our code organized.

justbuchanan commented 9 years ago

I've started a path-planning design doc to put ideas for our path-planning overhaul. Once the semester starts, we'll have have a meeting to discuss and architect this thing, but for now it's a good place for any brainstorming and possible solutions. Ping me if you don't have edit access.

https://docs.google.com/document/d/15fr7Nd7pkN3WY2ikKZYK-bsAn1ihBRnibBxLkrRl_bc/edit?usp=sharing

RoboJackets / robocup-software

Improved path planner #2