Questions tagged [motion-planning]

Motion planning (also known as the navigation problem or the piano mover's problem) is a term used in robotics for the process of breaking down a desired movement task into discrete motions that satisfy movement constraints and possibly optimize some aspect of the movement.

Filter by
Sorted by
Tagged with
18
votes
6answers
12k views

What is the difference between path planning and motion planning?

What are the main differences between motion planning and path planning? Imagine that the objective of the algorithm is to find a path between the humanoid soccer playing robot and the ball which ...
15
votes
2answers
947 views

Nearest-neighbor data structure for non-Euclidean configuration space

I'm trying to implement a nearest-neighbor structure for use in an RRT motion planner. In order to do better than a linear brute-force nearest-neighbor search, I'd like to implement something like a ...
14
votes
2answers
838 views

Does RRT* guarantee asymptotic optimality for a minimum clearance cost metric?

The optimal sampling-based motion planning algorithm $\text{RRT}^*$ (described in this paper) has been shown to yield collision-free paths which converge to the optimal path as planning time increases....
11
votes
3answers
3k views

With a 6-axis robot, given end-effector position and range of orientations, how to find optimal joint values

Given a six-axis articulated robot arm holding a tool at its end-effector, if I have a desired tool position and tool orientation, there will be exactly 1 solution to the inverse kinematics equation ...
8
votes
3answers
8k views

Is configuration space same as joint space?

For robotic manipulator like the one on the picture: are the configuration space and joint space equivalent? I am trying to understand difference between the two...
8
votes
1answer
475 views

Monte-Carlo Localization

I'm implementing Monte-Carlo localization for my robot that is given a map of the enviroment and its starting location and orientation. Mine approach is as follows: Uniformly create 500 particles ...
8
votes
1answer
203 views

Which spline function would be best suited for the trajectory of a differential drive

What's the best kind of spline that can be used for generating trajectory that can be adapted during execution time? The use case is having a differential drive which has to move towards a point (x,y,...
7
votes
2answers
1k views

Motion Planning vs. Control

Often I see positions for robotics companies split into planning and controls engineers. But motion planning and controls seem to have a lot of overlap. As I understand in motion planning the ...
7
votes
2answers
2k views

Choosing path planning and obstacle avoidance algorithm for 2D space

I am working on a 2D space where my robot needs to follow a trajectory while avoiding some obstacles. I've read recently about methods for path planning as "Vector Field Histogram" and the "Dynamic ...
7
votes
8answers
17k views

What is the difference between motion planning and trajectory generation?

What are the major differences between motion planning and trajectory generation in robotics? Can the terms be used interchangeably?
6
votes
1answer
3k views

Implementing a boustrophedon algorithm in a given room with obstacles

I have a mobile robot which is navigating around a room, I already have the map of the room. I am using the navigation_stack of ROS. I am using rotary encoders for odometry. I am fusing the data from ...
6
votes
3answers
2k views

restricting range of motion with complex constraints

I am looking for a way to restrict a robot's range of motion, using complex constraints such as not tearing of a cable attached to the robot. Take an articulated 6-axis robot arm as shown below, with ...
6
votes
2answers
1k views

Line following robot path planning

I have built a mobile robot with several ultrasonic sensors to detect obstacles and an infrared sensor to track a line as a path. I have written a simple algorithm to follow the line which works fine, ...
6
votes
1answer
211 views

Path planning for visual servoing

I am at moment trying to implement a visual servoing application. the robot I am using is a UR5, and TCP has a stereo camera mounted on to it. The idea is to move the end effector according to the ...
5
votes
4answers
4k views

What are the advantages of optimal control as opposed to control theory?

For a robot, say path planning in particular, what are the pros and cons of choosing classical control theory or optimal control (LQR for example) ?
5
votes
1answer
2k views

Difference between kinematic, dynamic and differential constraints

I would like to know the simple difference between kinematic, dynamic and differential constraints in robotic motion planning.
5
votes
5answers
2k views

What is the difference between 4-point and 8-point connectivity in graph based planning?

In graph-based planning (say, A*), states are connected to their neighbors. How should one decide whether to connect to the 4 neighbors or the 8 neighbors? What are the pros and cons of each ...
5
votes
2answers
664 views

Obstacle Avoidance while Navigating

I need some ideas for strategies or algorithms to apply on these strategies to perform obstacle avoidance while navigating. At the moment I'm doing offline path planning and obstacle avoidance of ...
5
votes
2answers
976 views

A Vector Field Histogram implementation in Python 2.7

I am trying to implement the Vector Field Histogram as described by Borenstein, Koren, 1991 in Python 2.7 using the SciPy stack. I have already been able to calculate the polar histogram, as ...
4
votes
2answers
342 views

Optimal-time acceleration sequence of a line-following robot following a moving obstacle

Say we have a line-following robot that has a moving obstacle in front, that is a one-dimensional problem. The moving obstacle is defined by its initial state and a sequence of (longitudinal) ...
4
votes
2answers
406 views

Motion planning from a given path

Many articles reference algorithms such as A*, PRM or RRT based planners to motion planning algorithms which seems unreasonable since it is still necessary to parametrize found path with time.I wonder,...
4
votes
2answers
650 views

Check collision between robot and environment in OpenRAVE

I have a robot arm in an environment. How can I check for collision between this robot arm and the environment?
4
votes
1answer
145 views

How is homotopy used in planning algorithms?

What is an intuitive understanding for homotopy? At what stage is homotopy (I understand it as stretching or bending of path) in a planning algorithm? Is homotopy involved, for example, while ...
4
votes
1answer
1k views

Velocity Model Motion in Matlab (Probabilistic Robotics)

I want to implement the velocity motion model in Matlab. According to Probabilistic Robotics page 124, the model is as following \begin{align*} \hat{v} &= v + sample(\alpha_{1} v^{2} + \...
4
votes
1answer
7k views

Maze Solving Algorithm For Mazes With Loops

I am trying to implement a line following robot that can solve mazes similar to the Pololu robots you can watch on youtube. My problem is the maze that I am trying to solve is looped and therefore ...
4
votes
1answer
1k views

ROS MoveIt!, virtual joints, planar joints, prismatic joints

I do have a robotic application, where a 7Dof robot arm is mounted on a omnidirectional mobile platform. My overall goal is to get MoveIt! to calculate a sequence of joint movements, such that the ...
4
votes
2answers
2k views

Navigating through a Maze using path-planning (Dijkstra)

I'm working on an robot that would be able to navigate through a maze, avoid obstacles and identify some of the objects in it. I have a monochromatic bitmap of the maze, that is supposed to be used in ...
3
votes
3answers
2k views

Working of Autonomous Lawn mower(ALM) in an unbounded area without a perimeter wire

I have an Autonomous Lawn mower(ALM) which can mow a certain lawn area when that area is bounded by a perimeter wire. Even when that perimeter wire is removed, it has to mow the above mentioned area ...
3
votes
1answer
322 views

Configuration space of rotating link

I have only recently started reading Steve LaValle's book on motion planning. It mentions that a rotating link with a fixed pivot has a configuration space of a unit circle. Since the configuration ...
3
votes
2answers
1k views

Lifting robotic leg with only one servo

Note before I start: I have not actually put anything together yet, i'm still just planning, so any changes that require a shape change or anything like that are accepted. I'm working on making a ...
3
votes
2answers
374 views

What is the difference between Obstacle Avoidance and Dynamic Path Planning?

I always assumed that obstacle avoidance refers to general prevention of collisions with any kind of obstacles, even without considering a goal for the decision how to execute an avoidance maneuver. ...
3
votes
1answer
141 views

How can we solve the problem of robot size in sensor based motion planning?

As you know in Bug algorithm there is a simplifying assumption that says the robot has no size and can fit between any arbitrarily small gap in the map. How can we overcome the challenge of robot size....
3
votes
2answers
389 views

Motion planning and robot controlling

I am stuck with understanding how can I make my robot move along planned path. For instance, if we have a grid map of an environment and applied, for example, A* to plan a path then after that we have ...
3
votes
1answer
1k views

State space and control space

I would like to know the difference between state space and control space in relation to motion planning. I would like a simpler explanation.
3
votes
1answer
267 views

Optimal-time trajectory in 2D and 3D with simple constraints

I'm trying to find the optimal-time trajectory for an object (point mass) from point p0 with initial velocity v0 to point ...
3
votes
1answer
116 views

Motion profile and Motion control scheme, how do they interact?

I'm studying motion control and I start with the simplest case, I have to go from A to B in a straight line using a trapezoidal motion profile. I understand that in a real case, due to the fact that ...
3
votes
3answers
116 views

Interference caused by multiple robots during task completion

Suppose there is an area to survey. If we deploy one robot it takes time T to sweep the area. Now if we deploy 2 robots, we would expect it to take time T/2. However in reality, because we are sending ...
3
votes
2answers
295 views

Motion planning with sequential convex optimization

I recently read a paper titled Finding Locally Optimal, Collision-Free Trajectories with Sequential Convex Optimization by John Schulman, Jonathan Ho, Alex Lee, Ibrahim Awwal, Henry Bradlow and Pieter ...
3
votes
2answers
390 views

Path planning of 2 arm 4dof Robot

I am working on path planning for a 2 arm 4dof (2 dof for each arm) robot. I am currently using a centralised planning methodology (considering the multi robot system as a single one with higher dof, ...
3
votes
1answer
841 views

Task space to joint motion space conversion

I am the moment trying to read and understand this paper Task Constrained Motion Planning in Robot Joint Space but seem to have a hard time understanding the math. The paper describes how to perform ...
3
votes
2answers
702 views

Difference between g-value and rhs-value in Lifelong Planning A*

What is the difference between g-value and rhs-value of Lifelong Planning A* algorithm? According to this link, D* Lite, g(s) directly correspond to the g-values of an A* search, i.e. g(s) = g(s') + ...
3
votes
2answers
441 views

why is quadrotor motion planning hard?

With introduction of incremental sampling algorithms, like PRM and RRT planning in higher dimensional spaces in reasonable computation time has become possible though it is PSPACE-hard. But why is a ...
3
votes
1answer
817 views

Determine the configuration space for a robotic arm

I'm working with a 4DOF Parallel-Mechanism arm. I'm interested in writing planners for this arm (PRM or RRT) in the configuration space, but I'm not sure how to identify obstacles/collisions. When ...
3
votes
1answer
517 views

Robot Navigation Feedback using Image Processing

In my project, I've successfully analyzed the arena and have detected the obstacles using an overhead webcam. I also have computed the shortest path. The path data is transmitted to the robot via ...
3
votes
1answer
478 views

Difference between Collision Cone and Velocity Obstacle

I'm trying to understand these two classic approaches to path planning in dynamic environments/with moving obstacles. According to some review papers, there seems to be quite a difference between them,...
3
votes
2answers
2k views

How to move a robot to a point while avoiding obstacles?

I am trying to move a robot in a straight line from point A, to point B. The robot's primary sensor is a Hokuyo URG-04LX-UG01 LIDAR that gives me the magnitude and direction of each point it detects ...
3
votes
1answer
191 views

Software for mission planning in multi-robot systems

I am interested in mission planning for multi-robot systems. Given multiple robots and multiple tasks and an environment, I need to specify missions and software should plan for the robot team to ...
3
votes
3answers
2k views

Generalized Voronoi Diagram

I need to compute the Voronoi diagram for a map with some obstacles but I can't find any pseudo-code or example in MATLAB. The "voronoi" function in MATLAB works with points, but in this case the ...
3
votes
1answer
231 views

Motion planning with Gaussian Process Regression

I was recently introduced to Gaussian Process Regression (GPR). I read multiple papers regarding use cases of GPR in robotics, however, they were more or less very limited. Use case from the ...
3
votes
1answer
141 views

Seminal work in multi-robot task decomposition [closed]

Multi-Robot task decomposition implies that there is a mission that needs multiple mobile robots like guarding the president's car with a team of drones. This high-level layman interpretation of the ...