ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО МАРШРУТА ДВИЖЕНИЯ МОБИЛЬНОГО РОБОТА

Т.С. Мицай

Рассмотрен алгоритм оптимального планирования маршрутов в общей постановке. Маршрут строится в виде итерационного процесса улучшения решений, причем на первом этапе для определения маршрута используется волновой алгоритм с вычислительной сложностью пропорциональной числу узлов графа. На следующих этапах алгоритма происходит уточнение маршрута за счет последовательного выполнения пространственной фильтрации матрицы накопленных затрат и матрицы направлений. Алгоритм завершает свою работу при стабилизации накопленных затрат для узлов графа. Быстродействие алгоритмов зависит от требуемой точности построения маршрута.

Ключевые слова: карта местности, планирование траектории, оптимальное движение, волновой алгоритм, взвешенный граф, накопленные расходы, алгоритм фильтрации.