3
$\begingroup$

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, 4 in this case) and A* algorithm to find the shortest path. The problem with this algorithm is its high computation time.Is there any way to reduce the computation time while still obtaining the shortest route ?

Note:decentralised path planning is not good enough for my case.

Improve this question
$\endgroup$
5
  • $\begingroup$ have you looked at other optimal planning algorithms? $\endgroup$
    – holmeski
    Commented Jul 13, 2016 at 14:23
  • $\begingroup$ What kind of computation times are you talking about? How many obstacles are there in the space? Or is it just arm-arm collisions to worry about? $\endgroup$
    – Ben ♦
    Commented Jul 13, 2016 at 16:15
  • $\begingroup$ @Ben . It is just arm-arm collision. There are no other obstacles and I have no trouble creating the configuration space. The time required for the algorithm to find the shortest path after getting the start and destination nodes is what i mean by computation time. Currently it takes about 5-6 seconds to compute the route. $\endgroup$
    – Arvind
    Commented Jul 14, 2016 at 3:45
  • $\begingroup$ @holmeski . I did look into other planning algorithms like Dijkstra's, artificial potential field and Probabilistic RoadMap, Found the A* to suite my purpose best. $\endgroup$
    – Arvind
    Commented Jul 14, 2016 at 4:19
  • $\begingroup$ @Arvind A* is by default faster than Dijkstra's in almost all situations to the best of my knowledge. In fact, Dijkstra's can be categorized as a variation of A* where the heuristic is 0 at all times. $\endgroup$
    – daniglezad
    Commented Oct 22, 2018 at 14:31

2 Answers 2

Reset to default
1
$\begingroup$

When I was using A* to navigate mobile robot in environment I've got this same issue. I am assuming that you are using cubic representation (nodes) of the environment where you have some cubes that represents free space and obstacles. What you can do is to increase the size of nodes that represents the environment. This way there will be less nodes the A* algorithm needs to process.

Another thing you can do is to cancel nodes that are unreachable by robotic arm or nodes you don't want the arm should move in.

Next thing is that after you get the path, the robotic arm will be moving as close as possible to the obstacles because in most scenarios it is the shortest path. You can solve this issue by increasing the transition value (cost) between the nodes near the obstacle.

Improve this answer
$\endgroup$
2
  • $\begingroup$ .Thanks for your answer, but Precision is also very important for my application. Increasing the size of the nodes results in reduced precision of the robot and also points in the physical space that are accessable will appear otherwise if I increase the size of the nodes. And I dont have any problem with the arms moving close to each other as long as they dont collide. $\endgroup$
    – Arvind
    Commented Jul 14, 2016 at 6:22
  • 1
    $\begingroup$ Then you can use one precision to move fast to your position and then if you are close to your position you can compute next path with higher precision but with using less nodes because you are closer to you location. Another thing that just came up to my mind is to use pre-computed paths and then just choose the one that is closest to your position and again compute the precision path after you are closer to the destination. Of curse this way it wouldn't be 100% optimal but it will be functional. $\endgroup$
    – Lubo
    Commented Jul 14, 2016 at 21:11
1
$\begingroup$

According to https://stackoverflow.com/questions/221311/what-is-the-most-efficient-way-of-finding-a-path-through-a-small-world-graph A* is one of the best algorithm. Other algorithm like RRT working with the same principle (generate a graph of possible moves and select the best). To improve the performance a datadriven approach could help. In the paper "Block A*: Database-Driven Search with Applications in Any-angle Path-Planning" this kind of algorithm is explained. Another possibility (which i prefer) is E-RRT which is described in "Bruce, James: Real-time randomized path planning for robot navigation, 2002". The implementation is difficult and the topic is under current research.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is wrong, RRT is not, in any way, a graph search algorithm. A* is. $\endgroup$
    – daniglezad
    Commented Oct 22, 2018 at 14:28
  • $\begingroup$ Path planning is a spatial graph search. The map contains of nodes which have a x/y coordinate and the solver is searching for the right sequence of nodes. $\endgroup$
    – Manuel Rodriguez
    Commented Oct 22, 2018 at 16:37
  • $\begingroup$ I disagree totally. You assume that path planning relies on discretizing the space, and this only happens with approaches like the grid-based ones. Apart from that generalization, RRT is meant to be used without any discretization (it is one of the advantages of sampling-based approaches over the grid-based ones). $\endgroup$
    – daniglezad
    Commented Oct 22, 2018 at 16:43
  • $\begingroup$ The runtime of RRT and A* is the same. That means, a loop is counting from 0 to 1000 and if the loop ends the path is planned. A* can be used for symbolic planning in abstract pddl-spaces as well. $\endgroup$
    – Manuel Rodriguez
    Commented Oct 22, 2018 at 17:08
  • $\begingroup$ I am not aware at all of PDDL planning, so maybe A* is used there as well as you say. About the first thing: when it is the same? In which situation? With which constraints? This is a far too general statement and probably wrong. About the loop example: I don't see how the runtime of rrt and/or A* (in a given problem of which we are not aware as a commenters) can be related to the loop-example you put. $\endgroup$
    – daniglezad
    Commented Oct 22, 2018 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.