Stack Overflow
Stack Overflow

Questions tagged [motion-planning]

Motion planning is the task of finding a continuous, collision free, path for an robot (entity) through a workspace that may contains obstacle, or reporting that no such path exists.

Resources for Learning More

In his response to a now-deleted Stack Overflow question, Andrew Walker writes:

The most comprehensive text I know of in this area is Steven LaValle's "Planning Algorithms", which is available from http://planning.cs.uiuc.edu/, as HTML and a PDF. Also included on the books webpage is a BibTeX file with more than a thousand references to the most significant literature in the field.

If you're looking for something a little more gentle, but no less comprehensive, you can check out the MIT Press book "Principle of Robot Motion Planning" by Choset, Lynch, Hutchinson, Kantor, Burgard, Kavraki and Thrun. Also of interest in robotics / sensing / motion planning is the excellent "Probabilistic Robotics" by Thrun, Burgard and Fox.

The classic text is "Robot Motion Planning" by Latombe, that has great coverage of the complete motion planning algorithms.

If you were looking for one place to start, I would have to recommend James Bruce's work on robocup and planning for autonomous systems, in particular his thesis "Real-Time Motion Planning and Safe Navigation in Dynamic Multi-Robot Environments" and the paper "Real-Time Randomized Path Planning for Robot Navigation". The work is presented in a way that makes it very approachable.

60 questions
15
votes
4 answers

Path generation for non-intersecting disc movement on a plane

What I'm looking for I have 300 or fewer discs of equal radius on a plane. At time 0 each disc is at a position. At time 1 each disc is at a potentially different position. I'm looking to generate a 2D path for each disc for times between 0 and 1…
Kaganar
  • 6,540
  • 2
  • 26
  • 59
7
votes
4 answers

What's a good Robotics Simulator?

So I'm currently doing some robotics research, and we have a custom built arm in the lab that we would like to simulate. I've done a little googling and wikipedia searching, and there seems to be a fair amount of open source and proprietary…
duckworthd
  • 14,679
  • 16
  • 53
  • 68
7
votes
1 answer

rapid exploring random trees

http://msl.cs.uiuc.edu/rrt/ Can anyone explain how rrt works with simple wording that is easy to understand? I read the description in the site and in wikipedia. What I would like to see, is a short implementation of a rrt or a thorough explanation…
AturSams
  • 7,568
  • 18
  • 64
  • 98
5
votes
4 answers

Algorithm for RC car

I'm looking for an algorithm, and I have no idea where to start! I'm trying to get from point A to point B in a cartesian graph. Movement is restricted to that of a RC car: backward, forward, forward-left, and forward-right (constant turning…
loneboat
  • 2,845
  • 5
  • 28
  • 40
5
votes
2 answers

How to avoid that the robot gets trapped in local minimum?

I have some time occupying myself with motion planning for robots, and have for some time wanted to explore the possibility of improving the opportunities as "potential field" method offers. My challenge is to avoid that the robot gets trapped in…
nesmoht
  • 125
  • 8
4
votes
1 answer

Time and space complexities of RRT and RRT*

What are the time and space complexities of RRT and RRT*? How does the incremental sampling based algorithms perform when compared to graph based incremental heuristic algorithms
J.Dow
  • 65
  • 4
4
votes
4 answers

Motion planning without a graph across an infinite plane

An object is positioned at A and wants to move to B. I want to calculate a movement vector there that doesn't move within the distance D of the to-be-avoided points in array C. So if the move vector (B-A) normalized and multiplied with the objects…
Mizipzor
  • 51,151
  • 22
  • 97
  • 138
3
votes
1 answer

Trajectory Planner with GEKKO is not able to handle given goal velocities

I have set up a Trajectory Planner for a vehicle with GEKKO, so basically i used a kinematic single-track model, which in nonlinear. It all works fine until i get to the part, when i give a goal velocity that is not equal to 0. I can give all other…
Flo
  • 33
  • 3
3
votes
1 answer

RRT algorithm in c++

I want to implement RRT for motion planning of a robotic arm. I searched a lot on the internet to get some sample code of RRT for motion planning, but I didn't get any. Can someone please suggest a good source where I can find RRT implemented in C++…
vacky
  • 277
  • 1
  • 4
  • 16
2
votes
2 answers

Pathfinding algorithms for continuous maps (e.g. polygons)

I try to investigate different algorithms for a short path between two points in a plane with polygonal obstacles. The vast majority of algorithms I found use discrete maps (Grid Map, visibility graph, Voronoi Roadmap, etc.). Some books (like…
umfundi
  • 95
  • 6
2
votes
0 answers

Finding optimal path

I am trying to find the optimal path for a car from given initial_state(of the form list[row,col,orientation]) to a given goal(of the form list[row,col]). The car is free to move forward in directions (up, left, down, right). It can perform 3…
Yash Raj
  • 21
  • 5
2
votes
3 answers

Finding best path given a distance transform

Given a distance transform of a map with obstacles in it, how do I get the least cost path from a start pixel to a goal pixel? The distance transform image has the distance(euclidean) to the nearest obstacle of the original map, in each pixel i.e.…
user3203860
  • 31
  • 4
1
vote
1 answer

Path Planner Algorthim with constraints?

Issue: Ran into an interesting problem at work today. I am trying to build a multi path planner algorithm with some interesting rules. I wanted to get the communities thoughts on approaches while I work on whatever I try first. Hoping this is a…
aris-t
  • 151
  • 8
1
vote
0 answers

Backward Value Iteration

I was reading LaValle's backward value interation but, completely failed to understand the example 2.9, which is mentioned in the text, works. Would someone be able to intuitively explain how backward value iteration works?
Kav
  • 85
  • 1
  • 1
  • 7
1
vote
0 answers

How to use Particle swarm optimization function (particleswarm) in MATLAB and why is my best function value shows an inf value?

I am new to MATLAB and making a project on Path Planning on a 3D environment with PSO. I managed to write my main function as : clc; close all; MaxIt = 100; noOfPointsInSolution = 1 ; n=(noOfPointsInSolution + 1) / 2 ; options =…
3kka-abhi
  • 11
  • 1
1
2 3 4