#grid #a-star #motion-planning
Вопрос:
Учитывая задачу планирования непрерывного движения по нахождению пути без столкновений от A до B, поиск A*, как известно, является оптимальным в сеточном приближении конечного размера, где каждая ячейка сетки, например, имеет 4 или 8 соседей.
Теперь путь A* может быть оптимальным, но он, безусловно, не обязательно должен быть точно таким же, как кратчайший путь в непрерывном пространстве, поскольку путь A* ограничен ячейками сетки и целочисленными координатами сетки. Теперь я бы ожидал, что если вы увеличите разрешение до бесконечности, то результирующий путь A* должен быть точным и равным непрерывной задаче. Но, глядя на литературу, я могу найти только «полноту разрешения» для аппроксимации на основе ячеек. Например, в «Обзоре алгоритмов планирования движения с точки зрения автономного наведения БПЛА» С. Герцен, З. Конг, Б. Меттлер Прямоугольное приближенное разложение клеток неоптимально, но с полным разрешением. Я действительно не понимаю, как это не оптимальное разрешение, то есть оптимальное, если вы увеличите разрешение до бесконечности.
Мой вопрос в том, действительно ли я неправильно интерпретирую это, или такое сеточное приближение действительно никогда не бывает точно оптимальным даже для бесконечных разрешений.
Комментарии:
1. Не существует такой вещи, как бесконечное разрешение. Существует только предел, поскольку разрешение приближается к бесконечности. Для линии 45 градусов, использующей путь с 4 соседями, путь, выбранный A*, всегда в 2 раза длиннее идеального пути, независимо от того, насколько близко разрешение к бесконечности. Это потому, что даже когда разрешение приближается к бесконечности, вы можете позволить уровню масштабирования также приближаться к бесконечности и по-прежнему видеть ступени лестницы на пути A*.
2. Но с увеличением разрешения A*-путь становится ближе (с точки зрения длины) к точному пути, не так ли? Могу ли я тогда получить такое хорошее приближение точной длины пути, как я хочу, даже если A*-путь никогда не будет точным?