Is a grid-approximation with A*-Search of a continuous motion planning problem resolution-optimal?

58 Views Asked by At

Given a continuous motion planning problem of finding a collision-free path from A to B, the A* search is known to be optimal on a finite sized grid-approximation, where each grid-cell for example has 4 or 8 neighbours.

Now, the A* path might be optimal, but it certainly doesn't have to be exactly the same as the shortest path in continuous space, since the A* path is confined to the grid-cells and integer grid coordinates. Now, I would expect that if you increase the resolution to infinity, the resulting A* path should be exact and equal to the continuous problem. But looking at the literature, I can only find "resolution-completeness" for the cell-based approximation. For example in "A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance" by C. Goerzen, Z. Kong, B. Mettler the Rectanguloid Approximate Cell Decompositon is non-optimal, but resolution-complete. I really don't understand how it's not resolution-optimal, meaning optimal if you increase the resolution to infinity.

My question is whether I am actually interpreting it wrongly or if such a grid-approximation is really never exactly optimal even for infinite resolutions.

0

There are 0 best solutions below