Аннотация: При создании мобильных роботов одной из центральных проблем является автоматическое планирование маршрута. Эта задача состоит в том, чтобы при заданных начальном и конечном положениях робота по карте местности построить маршрут, по которому робот может попасть в целевую точку, не столкнувшись с препятствиями. Существуют два подхода к решению этой задачи. В одном из них используется понятие конфигурационного пространства, идея которого состоит в том, чтобы стянуть объект (робот) в точку, одновременно расширив препятствия в соответствии с его формой. Кратчайший маршрут отыскивается путем просмотра графа «прямой видимости», в котором представлены все прямолинейные отрезки пути, обходящие препятствия в конфигурационном пространстве. Основным недостатком данного подхода являются трудности, возникающие при поворотах робота, и, кроме того, кратчайший маршрут проходит очень близко к препятствиям.

Ключевые слова: Робот, декомпозиция, планирование маршрута, проходимая область.