• Create Account

## Advanced pathfinding with robot in 3D

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

24 replies to this topic

### #21snowmanZOMG  Members

1205
Like
0Likes
Like

Posted 14 September 2012 - 12:36 PM

The author was one of my professors while I was in school. He's very smart. I find the book very useful for understanding the problems at a theoretical, abstract level, but it has very little to offer (perhaps none) when it comes to code examples. If you're mathematically inclined, you shouldn't have any problems.

### #22Emergent  Members

982
Like
1Likes
Like

Posted 28 September 2012 - 06:57 AM

I'm with snowman. As a starting point, I always direct people to Steve LaValle's book. Another very good book is this one.

The state of practice for robot planning is essentially this:

1. Use an RRT to generate some path -- any path -- in the configuration space (i.e., space of joint angles) from start to goal. The resulting path will not be optimal in any sense, but it can be computed quickly and it gets from point A to point B, which is the most important thing.

2. Smooth the path. There are varying strategies for this, and there is a little less consensus about the details, but the gist is that you do some combination of throwing out intermediate points in the path, and running splines (usually cubic) through the remaining points. In lower dimensions, this is what algorithms like "string pulling" aim to solve.

3. Write a feedback controller to follow the path. The standard methods (which are very similar) are "inverse Jacobian" and "Jacobian Transpose" controllers (the first reasonable Google hit is here; I also particularly like this book.)

There are some variations for the various items above, especially for part 1: Along similar lines to RRTs, there are also algorithms like RRG* that attempt to grow a random graph, and attempt to converge to a path that is actually optimal. This paper by Frazzoli's student should point you in the right direction (see the references). There are also some deterministic planners that people have had some success with; these do a combination of graph search and graph refinement (in the style of hierarchical A*).

### #23Emergent  Members

982
Like
0Likes
Like

Posted 28 September 2012 - 07:01 AM

Sorry, two links got removed from my last post in point 3; they were:

3. Write a feedback controller to follow the path. The standard methods (which are very similar) are "inverse Jacobian" and "Jacobian Transpose" controllers (the first reasonable Google hit is here; I also particularly like this book.)

### #24Fuzsy  Members

136
Like
0Likes
Like

Posted 30 September 2012 - 01:19 PM

Thanks Emergent,

I am currently learning a lot from replies, links and books I got here at the forum.

I have managed to get something working but there is still a long way to go. My current solution is based on Hierarchical A*.

My goal is to be able make a motion plan in less than 1 second. At the moment I am down to a average of 450 ms, but out of 1400 test positions 50 fails to find a plan. At least within 40 seconds.

40 seconds equal approximately 6000 branches searched.

I will look in to RRT. It seems like something I could use. Thanks again.

### #25Emergent  Members

982
Like
0Likes
Like

Posted 30 September 2012 - 05:49 PM

Oh! Also: Although I 100% understand if you want to write your motion planner from scratch as a learning experience, you might want to be aware of two existing pieces of software that can make your life easier:

1. ROS: The Robotic Operating System. This runs on top of Linux and manages message-passing, etc; it gives a modular way to write robotics software.

2. OMPL: The Open Motion Planning Library. This implements a variety of planners including RRTs, and is available as a ROS package.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.