Adaptive D* turn cost

[bensmith]

Hi,

I'm making an autonomous robot using LabView and have a question about the Adaptive D* path planning.

The robot is to travel in an arena with a checkerd floor, and to make the position tracking easier I have said it can only travel horizontally and vertically, I have made a small modification to the VI NI_Robotics_OccupancyGridWorldMap.lvclass:GetNeighbours.vi to make it return a very high edge cost for diagonal movement, and this works great.

What I want to do now is make a tile more expensive if it requires a change of direction so that my robot does not continue to zig-zag across the arena but rather drive in a large rectangle.

Is this easily possible?

Regards,

Ben Smith

[RoboticsME]

Great question.  There might be some ways to account for cost in changing direction, but I'm not sure how that would work.  Are you looking to find something that is guaranteed to be the most efficient?  Or would something that simply helps account for turning be suitable?    If the latter is true, you could consider combining Adaptive D* with localized potential fields.  The destination of the Adaptive D* path that is within the known/explored area could act as your intermediate destination (let's call intGoal).  If you set intGoal with a low potential, obstacles with a high potential (or neutral potential), and your robot with a high potential, then the resulting vectors should be able to guide your robot.  Imagine that you define a room where your robot is at one corner, and at the other corner is the point on the Adaptive D* path that is closest to the goal that you can still "see."  Then imagine that your robot is pumping a ton of water in to the room and all of it is draining away at the other corner.  All you have to do then is follow the flow of water, which happens to take the path of least resistance and also accounts for changing direction.

Cheers,

Karl

[S_Kamath]

First beware the potential pitfalls of modifying code in vi.lib. Any changes that you make there will be particular to your computer. It is not easily portable since others may depend on the stock functionality on the other computer. I do not recommend modifying vi.lib files unless you are sure you will never be moving code to a different computer, and you do not expect other peoples code to work correctly on your computer.

That said let me address the technical issues:

An assumption of the AD* planning algorithms is that the cost to get from one point to another is solely depended on the origin node,destination node, and edge costs. Changing the cost depending on the previous "hop" in the path would be very difficult (every data structure that stores "current best" costs would have to store multiple such values depending on direction of previous hop). I highly discourage this approach.

One other method is to ensure that in case of tied cost paths that are "straight" are preferred to paths that are "bent". This does not provide the strong guarantee that you are looking for but may be useful. This is likely to require lots of modification to the underlying files and is not recommended.

Lastly, the best solution is to change to a directed graph with two nodes for every grid square. One node represents a robot facing north and the other represents a robot facing west. The cost for getting from (0,0,N) to (1,0,N) is 1 but the cost to get to (1,0,W) is greater than 1. This method will bias the result towards straight paths.

[bensmith]

Hi,

Thanks for the replys

I'm aware that changing the core modules is not a good idea, but the program will only ever be deployed from this one computer, and it is a quick modification that can easily be reverted if needed.

Your best solution sounds very interesting but I don't think I have time to implement it before the competition, how it now works is ok and is barley noticable when there are many obstacles as the long "diagonal" paths are broken up anyway.

I might try to fix this after the competition.

Thanks again for the detailed reply.

[bensmith]

I have implemented the directed graph method and it is working great, thanks for the idea!

However, the path will not take into account changes to edge costs unless the overhaul flag is set on the AD* vi, is this the correct behaviour?

[timtamslam]

Hey bensmith,

Based on my understanding of the AD* VI, i'm not sure if the overhaul input should function that way. How I understand it is the overhaul is basically used when your map drastically changes so you can more efficiently replan your path. Is your choice in the overhaul settings causing the path planning to not work out correctly?

[bensmith]

When overhaul is set to false the path will not update correctly, it seems to be not noticing the changes to the map at all.

As soon as it is set to true the path updates correctly to account for new obstacles but obviously takes longer to evaluate.

I will make an example program when I get time to show this behaviour.