Планировщик маршрута для антропоморфного робота в условиях неизвестного окружения.
Необходимо прокладывать маршрут в условиях более сложных, чем просто ровный пол и препятствия. Для антропоморфных роботов тут предлагают различные footstep-планнеры, которые прокладывают маршрут в виде набора шагов. По ряду причин этот метод не всегда подходит и просто не очень мне нравится:
- Требуют от РТС возможности совершать именно эти запланированные шаги
- Каждый следующий шаг зависит от предыдущего, если выполнение не точное, то погрешность растет
- ???
Разделить планер на две составляющие: глобальный и локальный. Глобальный планер не планирует непосредственно движения робота, а строит траекторию. Для планирования траектории предварительно строится на основе 3D карты и, возможно, дополнительных данных, карта весов. Карта весов показывает грубую оценку возможности робота пройти в данном месте.
Робот движется по траектории с использованием локального планера, который, в идеале, совмещает генерирование движений с выполнением условий равновесия и не-коллизий с окружающей обстановкой.
Глобальный планер делает грубую оценку, вплоне может быть так, что когда робот подойдет ближе, станет ясно, что это не преодалимо для него. Ну и ладно, развернется и будет искать другой путь. Такой подход основан на аналогии с человеком: когда мы планируем траекторию, мы приблизительно оцениваем, что мы можем преодалеть, а что нет, не задумываясь о движениях тела на протяжении всего маршрута.
Карта разделяется на клетки определенного размера и расчитывается возможность совершения перехода из одной клетки в другую (в соседнюю). При этом не обязательно a -> b == b -> a (пример: спрыгнуть с уступа). Таким образом, карта превращается в направленный взвешенный граф. Скорее всего, не надо определять веса для всей карты сразу, а определять их по ходу работы путепрокладывающего алгоритма (например, A* как самого простого). Полученные результаты кешируются для последующих поисков. В случае изменения участка карты, клетки в этом участке удаляются из кэша. Если через этот участок проходил путь, он перестраивается.
В качестве мертики при прокладке пути можно взять взвешенное расстояние, но, возможно, применить более сложную метрику из двух независимых компонент: расстояни и сложность (средняя\максимальная\минимальная итп) сложность. Это позволит настраивать предпочтения: более короткий путь и сложный, или более простой и длинный.
Считать неизвестные ячейки открытыми и прокладывать через них путь напрямик, при обновлении карты перестраивать путь.
Все описанное хорошо подходит для условно-двухмерного окружения - могут быть перепады высот, но не может быть несколько точек с разной Z по одинм (x, y) (как в Doom). Для получения возможности планировать движения в полноценном 3D пространстве (например, несколько этажей) необходимо заменить двухмерную карту на трехмерную, а клетки на воксели.
Переход из некого вокселя (x, y, z) -> (x, y, z + 1) невозможен, потому что робот не умеет летать.
ВНИМАНИЕ:
А если робот умеет прыгать, и в определенных условиях прыжок может помочь ему преодалеть
препятствие? Прыжок вверх на пустом месте ничего не изменит (из прыжка прыгнуть нельзя), но это будет
постоянная проверка прыжков на каждый воксель. Тут нужна оптимизация.
Хороший вопрос, и ответ на него: "Я не знаю". Здесь явно не подходит упрощение 3D карты до 2D, как делается в том же footstep_planner, необходимо оценивать само облако точек\октомап.
Какая-то обучаемая регрессионная дичь, выдающая сложность [0; 1]. Обучаемость против жесткого алгоритма дает возможность дообучать механизм в процессе работы: когда робот подошел ближе и локальный планер подтвердил проходимость, или наоборот, сделал вывод о невозможности пройти, эти данные можно добавлять в обучающую выборку.