Геометрия для робототехники и GIS

Когда Uber запрашивает ближайших водителей - это задача computational geometry на базе данных из 100 миллионов строк в реальном времени. Когда беспилотный автомобиль Waymo планирует объезд препятствия за 50 миллисекунд - это RRT в 12-мерном пространстве конфигураций. Когда Google Maps строит маршрут через Москву - это A* на графе дорог с геопространственным индексом. Вычислительная геометрия в робототехнике и GIS - это не академия, это core infrastructure миллиардных компаний.

• **Uber, Lyft, Яндекс Go:** R-tree индексы для поиска ближайших водителей в реальном времени. S2 cells для геохэшинга зон спроса
• **ROS (Robot Operating System) / MoveIt:** RRT* и OMPL (Open Motion Planning Library) для планирования траекторий манипуляторов в 6-12-мерном C-space
• **PostGIS / BigQuery GIS / Snowflake:** пространственные расширения SQL с R-tree индексами и полным набором операций вычислительной геометрии для аналитики геоданных

Планирование движений: RRT и PRM

Робот-манипулятор с 6 степенями свободы должен переставить деталь, не задев соседние объекты. Пространство конфигураций (C-space) - это множество всех возможных состояний робота, размерность которого равна числу степеней свободы. Препятствия в реальном пространстве порождают запрещенные зоны в C-space. Планирование движения - это поиск пути в C-space от начального до конечного состояния. RRT (Rapidly-exploring Random Tree) строит дерево случайными сэмплами: на каждом шаге случайная точка притягивает ближайший узел дерева, и новый узел добавляется если путь свободен.

RRT вероятностно полон: если путь существует, RRT найдет его при достаточном числе итераций. RRT* добавляет оптимизацию: перепрокладывает ветки для минимизации стоимости пути. Сложность: O(n log n) на n итераций. Используется в ROS (Robot Operating System), Drake (MIT), MoveIt.

Пространство конфигураций и минковская сумма

Пространство конфигураций (C-space) превращает задачу 'робот с препятствиями' в задачу 'точка в препятствиях'. Препятствие P в рабочем пространстве при форме робота A порождает C-obstacle = P (+) (-A), где (+) - минковская сумма. Минковская сумма двух выпуклых тел - выпуклое тело, сумма радиусов которого равна сумме радиусов слагаемых. Для робота-диска радиуса r минковская сумма с препятствием P - это P, расширенное на r. Это основа алгоритма inflated map в навигации мобильных роботов.

Минковская сумма двух выпуклых полигонов с m и n вершинами вычисляется за O(m+n) через слияние отсортированных граней. Для невыпуклых тел сложность O(m*n). На практике для 3D: Bullet Physics и FCL используют GJK (Gilbert-Johnson-Keerthi) для проверки коллизий без явного построения C-space.

Геоинформационные системы: алгоритмы и форматы

GIS (Geographic Information Systems) - прикладная вычислительная геометрия в масштабе планеты. Google Maps, OpenStreetMap, QGIS работают с геометрией на сфере Земли. Ключевые задачи: буферизация (Minkowski sum полигона с диском), наложение (boolean операции над полигонами), маршрутизация (A* на взвешенном графе дорог), point-in-polygon (ray casting для определения региона). Проекции (Mercator, UTM) искажают либо площади, либо углы - нет проекции без потерь (теорема Гаусса снова).

Shapely (Python) и GEOS (C++) реализуют полный набор операций вычислительной геометрии для GIS: buffer, union, intersection, difference, simplify, contains, covers. PostGIS расширяет PostgreSQL геопространственными типами и индексами (R-tree). GeoPandas объединяет Pandas и Shapely для анализа геоданных.

Пространственная индексация: R-tree и S2

База данных Uber хранит миллиарды поездок с геокоординатами. Запрос 'все водители в радиусе 1 км от пользователя' должен выполняться за миллисекунды. Полный перебор - O(n), где n может быть 10 миллионов. R-tree решает задачу: иерархия bounding boxes позволяет отсекать целые регионы. S2 (Google) - альтернатива: делит сферу на клетки через проекцию на куб и кривую Гильберта, сохраняя пространственную локальность в 1D ключах. Uber H3 - гексагональная иерархическая сетка для аггрегации.

R-tree: вставка O(log n), запрос по прямоугольнику O(log n + k) где k - число результатов. PostGIS использует GIST-индексы (обобщенные R-tree). S2 cells: 30 уровней иерархии, уровень 0 = 1/6 сферы (~85 млн кв. км), уровень 30 = ~0.5 кв. мм. Квери: contains, intersects, nearest neighbor.

Ключевые идеи

• **RRT/RRT*:** вероятностно полное планирование движений в высокоразмерном C-space. Стандарт в ROS, Waymo, Boston Dynamics.
• **Минковская сумма:** ключ к упрощению задачи коллизий - расширить препятствия на размер робота и планировать точку.
• **GIS алгоритмы:** буферизация, наложение, point-in-polygon - Shapely/GEOS в Python, PostGIS в SQL, все базируются на алгоритмах вычислительной геометрии.
• **Пространственная индексация:** R-tree для polygon queries, S2/H3 для геохэшинга. Составной B-tree по (lat, lon) - антипаттерн для геозапросов.

Связанные темы

Прикладные задачи робототехники и ГИС опираются на алгоритмы вычислительной геометрии.

• Range Search и kd-деревья — Пространственные индексы в низкоразмерных пространствах; kd-tree альтернатива R-tree для точечных запросов
• Nearest Neighbor Search — kNN поиск в GIS и RRT - одна задача в разных контекстах

Вопросы для размышления

• RRT работает в непрерывном C-space, A* - на дискретном графе. Какой подход лучше для планирования маршрута пешехода в городе? Для манипулятора на заводе? Что определяет выбор?
• Uber использует S2 cells, а не R-tree для геохэшинга зон. S2 сохраняет пространственную близость в 64-битном ключе. Какие операции становятся проще с S2 по сравнению с R-tree? Какие сложнее?
• Беспилотные автомобили должны планировать движение в реальном времени (50 мс) в высокоразмерном C-space. RRT* вероятностно полон, но не детерминирован. Допустимо ли это для safety-critical систем? Как Waymo решает эту проблему?

Связанные уроки

• rob-01