Введение 3
Постановка задачи 6
Глава 1. Обзор существующих методов построения маршрута 7
1.1. Алгоритмы на основе графов 7
1.2. Методы на основе клеточной декомпозиции 12
1.3. Методы на основе потенциальных полей 16
Глава 2. Алгоритм построения маршрута 19
2.1. Описание алгоритма 19
2.2. Анализ работы алгоритма 23
Заключение 28
Список литературы 29
Впервые о мобильных роботах заговорили после успешной миссии Лунохода-1 [1], который стал первым успешным планетоходом, предназначенным для исследования поверхности луны. Он был доставлен на поверхность Луны 17 ноября 1970 года на борту посадочного модуля Луна- 17. Им управляли специально обученные операторы удаленного контроля с Земли. Луноход-1 преодолел расстояние около 10 километров.
В настоящее время, благодаря развитию информационных технологий, мобильные роботы используются не только для космических миссий, а также и в различных отраслях деятельности человека. Например, мобильные роботы используются для погрузки и разгрузки товара на складе. Благодаря тому, что расположение стеллажей на складе не меняется, робот может спокойно маневрировать между ними, не создавая аварийных ситуаций.
Известны примеры использования роботов для обеспечения безопасности человека. В Японии распространены, так называемые, роботы- полицейские, которые движутся по городу и следят за соблюдением порядка на улицах. Они оснащены детекторами дыма, способны издавать сигнал тревоги, а также оснащены средствами видеосъемки.
В 1989 году [2] был изобретен первый автономный робот Helpmate, предназначенный для решения логистических и транспортных задач в больницах. Навигация Helpmate осуществлялась на основе одометрических данных, а с помощью ультразвуковых датчиков измерения расстояния, датчиков инфракрасного излучения и видеокамер робот был способен избегать столкновений с препятствиями. Он использовался для доставки еды и лекарств пациентам в палаты, перевозки документов среди медперсонала больницы.
Компания Meituan Dianping, которая первоначально выступила с инициативой «бесконтактной доставки» по Китаю, уже начала использовать автономные транспортные средства для поставок продуктов в районе Шуньи 3 в Пекине и планирует запустить аналогичные службы доставки роботов в других районах столицы [3]. Компания начала тестировать роботов и беспилотников для доставки в 2019 году, но это первый случай развертывания автономных средств доставки на дорогах общего пользования. Автономный робот способен перевозить до 100 кг товаров и доставлять от трех до пяти заказов за каждую поездку.
Также широкое распространение имеют роботы, предназначенные для работы в среде, опасной для жизни человека. Например, роботов используют при устранении последствий техногенных катастроф, для работы в местах с повышенным уровнем радиации, для участия в противотеррористических операциях.
Роботы используются для диагностирования, фрезерования и заделки трубопроводов изнутри. Самоходные роботы позволяют быстро находить проблемы, получать достоверную информацию о текущем состоянии трубопроводов, принимать правильное решение о способе ремонта и объеме предстоящих работ.
Построение маршрута движения является одной из важнейших задач в навигации роботов. В основе решения данной задачи лежат три главных условия. Первое - построенный маршрут должен проходить через заданные начальные и конечные точки. Второе - путь робота необходимо строить таким образом, чтобы он не пролегал через ограничения, такие как различные архитектурные сооружения, препятствия природного характера и так далее. И, наконец, третье - построенный маршрут, отвечающий первым двум условиям, должен быть оптимальным.
Подходы к планированию пути можно систематизировать по разным аспектам. В отношении применения информационных технологий, методы возможно разделить на традиционные и эвристические. По имеющейся информации об окружающей среде допускается разделение на подходы с глобальным планированием маршрута (в прямом доступе есть карта местности) и локальным планированием (в наличии сведения об обстановке в области прямой видимости робота). В зависимости от характера окружающего мира можно классифицировать задачи планирования с учетом динамических и статических ограничений (стоит сказать, что при решении практических задач, только статические ограничения почти не встречаются).
В данной работе ставятся задача построения маршрута с учетом динамических ограничений, а также разрабатывается алгоритм для ее решения. Для иллюстрации работы алгоритма приводятся смоделированные примеры.
В работе рассмотрены основные подходы к решению задачи построения маршрута с динамически меняющимися ограничениями, а именно методы на основе графов, алгоритмы на основе клеточной декомпозиции и подходы на основе потенциальных полей. Проведен анализ рассмотренных методов, а также выбран наиболее оптимальный подход для решения поставленной задачи.
Предложен алгоритм построения маршрута с учетом динамических ограничений, основанный на клеточной декомпозиции.
Предложенный алгоритм реализован на языке программирования Python, с использованием библиотеки pygame для моделирования. Проведено тестирование работоспособности алгоритма в различных ситуациях.
