search

ssardina-research / p4-simulator

Python Path Planning Project (P4)
GNU General Public License v3.0
4 stars 2 forks source link

Cost system allowing wrong diagonals? #10

Closed ssardina closed 9 years ago

ssardina commented 9 years ago

Original report by Sebastian Sardina (Bitbucket: [Sebastian Sardina](https://bitbucket.org/Sebastian Sardina), ).

I have fixed the bug with uniform variable and improved substantially how costs are set. However, there is still something strange, seems some diagonals are allowed where it should not. A* uses p4-internal cost and it returns a path that is cheapest that the optimal:

#!python

[ssardina@ssardina-Latitude-E7440 src]$ python p4.py -m ../maps/bloodvenomfalls.map  -s 459,444 -g 79,241 -a agents-main/agent_astar 

Total Cost : 490.4701 | Total Steps : 401 | Time Remaining : inf | Total Time : 1.297272

The real cost should be 491.0559 as returned by the JPS-Patric which computes cost itself:

#!python

[ssardina@ssardina-Latitude-E7440 src]$ python p4.py -m ../maps/bloodvenomfalls.map  -s 459,444 -g 79,241 -a agents-main/agent_jps_patric

Total Cost : 491.0559 | Total Steps : 402 | Time Remaining : inf | Total Time : 0.148358

variable self.uniform is TRUE in both cases so that we are in the standard setting. See that A* does 1 step less and the difference in cost is a diagonal move vs 2 straight moves. But why??? Maybe you can see it more clear than me. Does it have to do with corner-cutting maybe?

ssardina commented 9 years ago

Original comment by Sebastian Sardina (Bitbucket: [Sebastian Sardina](https://bitbucket.org/Sebastian Sardina), ).

I know why! With the new way of dealing with WATER (not passable from other terrains) it is not checking for corner cutting across water. Here is the image:

corner.jpg

So all is going well except corner-cutting across water. this should not be allowed

ssardina commented 9 years ago

Original comment by Sebastian Sardina (Bitbucket: [Sebastian Sardina](https://bitbucket.org/Sebastian Sardina), ).

Fixes #10 - improved cost model of water - default is inf unless it is coming from water

ssardina commented 9 years ago

Original comment by Sebastian Sardina (Bitbucket: [Sebastian Sardina](https://bitbucket.org/Sebastian Sardina), ).

Fixes #10 - improved cost model of water - default is inf unless it is coming from water

ssardina commented 9 years ago

Original comment by Sebastian Sardina (Bitbucket: [Sebastian Sardina](https://bitbucket.org/Sebastian Sardina), ).

Fantastic, works!