3D Map

[vanAken]

How to use a 3D=2D(t) map with moving obstacles?

[vanAken]

int world_map[ MAP_WIDTH] [MAP_HEIGHT] [MAP_TIME ] = {
{ 's', '1', '9','9', '1', '1' }, { '9', '1', '1','1', '9', '1' }, { '1', '9', '1','9', '1', '9' }, { '9', '1', '9','9', '1', '1' }, { '9', '1', '1','1', '9', '1' }, { '1', '9', '1','9', '1', '9' }
}, { { '9', '9', '1','9', '9', '1' }, { '1', '9', '1','1', '1', '1' }, { '9', '1', '1','1', '9', '9' }, { '1', '9', '1','1', '1', '1' }, { '9', '9', '9','1', '9', '9' }, ...... }
}
}

[justinhj]

Hi Van

Not sure what you mean by 3d to 2d map, can you explain more?

Moving obstacles change the best path between points so you essentially have to run A* on the map every time the obstacles move.

There is in fact a variant of the A that handles changing environments called D, but I don't know anything about it.

Justin

[vanAken]

Hi Justin, I'm a UDACity student in Term3. The biggest challenge is the path planing Project. Here is a Solution: https://github.com/ericlavigne/CarND-Path-Planning. The road is in frenet coordinat system, with s and d. S is the length of the road and d is the distance from the mid road spline. Than I discrete the road in 4m x 4m squares and place the other cars form sensor fusion data as a start map. Now I create 10 new maps each for every future second. With the relative velocity I can calculate the movement of the other car and place them in the map. Now A came in the game and has to find the fastst way to the horizon. The ego_car can move left and right [-1, 0, +1] and accelerate witch results in moves in s the road direction [-2, -1 , -0, +1, +2 ]. This vector has to be update after every move on the next map, because v_max limits the max speed. Than we have a nice 3DIM A :-) not A4DIM like ERIC (s,d,v,t) and not A5DIM (x,y,raw,v,t)(raw = orientation agle) witch make that idea impossible. Around the car there will be some higher numbers to ensure safety distance and so on... That why I like your code beside the speed. Not easy, but you made a nice fast A and can understand that - I hope my English will be OK. Please ask if something is not clear. I like this SDC course very much and want to make a new solution of the problem. I will read for D Sometimes breaking is the fastes way to the goal. Best Volker

[vanAken]

Here is an D*. Maybe that is a next step forward, because it promise to be faster. (t_max 0.2sec) http://www.cs.cmu.edu/~motionplanning/lecture/AppH-astar-dstar.pdf I found a first code example, here: https://github.com/ArekSredzki/dstar-lite/blob/master/Dstar.cpp But in general I like your code and want to go ahead with it. For each second and each step I have to go a map higher and project the path down at the end.

Dear Justin, please help me and let me know, is that working? The ego_car can move in three dimension: 1.) left and right [-1, 0, +1] 2.) up and down [-2, -1 , -0, +1, +2 ] s = f (v, a, t and v_max , v_min). 3.) time [+1] - just forward ;-) Where to place the allowed moves for the expansion list?

Best Volker

[vanAken]

However I start in 2D and will see how it works. Than I try to add some deterministic moves in 3D and tell you, how it look like. Maybe here is not the right place for that, so please let me know.

[justinhj]

Hi again Just caught up with your messages and read about frenet coordinates.

For what I understand your idea sounds like it will work, so just keep going and let me know if you need help using my code.

The only difficulty I can foresee is if the search space is too large... each step you can steer left and right, accelerate or decelerate, so I assume you're breaking those into discrete steps?

[justinhj]

I'd like to close the issue since it's not a bug or feature request and you can continue chatting on this new gitter community

https://gitter.im/astar-algorithm-cpp/community#

[vanAken]

Yes, please close it and thank you. Meanwhile I make some Progress and found what I'm looking for // push each possible move except allowing the search to go backwards I'll start with big squares 4x4m x 1second with a size of 12mx200mx60s = 9000 Cubes, that is less than 100x100 squares.
Eric and you, Justin are using "Priority Queue" which make you both a Pro!

[vanAken]

Hi Justin, many thanks for this library. Here is how my result looks like. https://github.com/vanAken/CarND-Path-Planning-Project/blob/master/nice_after100miles-2019-05-21_23.55.05.mp4

[justinhj]

That looks very interesting, thanks for sharing!

I will add a link to your project to my astar projects page.

On Sat, 25 May 2019 at 12:59, vanAken notifications@github.com wrote:

Hi Justin, many thanks for this library. Here is how my result looks like.

https://github.com/vanAken/CarND-Path-Planning-Project/blob/master/nice_after100miles-2019-05-21_23.55.05.mp4

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/justinhj/astar-algorithm-cpp/issues/21?email_source=notifications&email_token=AAFX3IYSDG7X7NLOLOK2KVDPXGLAPA5CNFSM4GZGLIH2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWHYHQA#issuecomment-495944640, or mute the thread https://github.com/notifications/unsubscribe-auth/AAFX3I5ONGRJGX6XGHWBLCTPXGLAPANCNFSM4GZGLIHQ .