Если у робота, путешествующего к месту назначения, есть только два возможных пути, ему нужно только сравнить время путешествия по маршрутам и вероятность успеха. Но если робот перемещается по сложной среде со множеством возможных путей, выбор лучшего маршрута в условиях такой неопределенности может быстро стать неразрешимой проблемой.
Исследователи Массачусетского технологического института разработали метод, который может помочь этому роботу эффективно определять наилучшие маршруты к месту назначения. Они создали алгоритм построения дорожных карт в неопределенной среде, который балансирует компромисс между качеством дорожных карт и эффективностью вычислений, позволяя роботу быстро находить проходимый маршрут и минимизировать время в пути.
Алгоритм начинает с маршрутов, которые наверняка безопасны, и автоматически находит кратчайшие пути, по которым робот может пойти, чтобы сократить общее время в пути. В ходе смоделированных экспериментов исследователи обнаружили, что их алгоритм может обеспечить лучший баланс между производительностью и эффективностью планирования по сравнению с другими базовыми показателями, в которых приоритет отдается одному или другому.
Этот алгоритм может найти применение в таких областях, как исследования, например, помогая роботу спланировать лучший способ добраться до края далекого кратера по неровной поверхности Марса. Это также может помочь поисково-спасательному дрону найти кратчайший путь к человеку, застрявшему на отдаленном склоне горы.
«Нереально, особенно в очень больших открытых пространствах, точно знать, где можно, а где нельзя пересекать. Но если у нас есть хотя бы немного информации о нашей окружающей среде, мы можем использовать ее для построения высококачественной дорожной карты», — говорит Ясмин Вейс, аспирантка электротехники и информатики (EECS) и ведущий автор статьи по этому вопросу. техника.
Вейс написал статью вместе с Мартиной Стадлер Курц, аспиранткой факультета аэронавтики и астронавтики Массачусетского технологического института, и старшим автором Николасом Роем, профессором аэронавтики и астронавтики Массачусетского технологического института и членом Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (CSAIL). Исследование будет представлено на Международной конференции по робототехнике и автоматизации.
Создание графиков
Чтобы изучить планирование движения, исследователи часто думают об окружающей среде робота как о графике, где серия «ребер» или отрезков линий представляет возможные пути между начальной точкой и целью.
Вейс и ее коллеги использовали графическое представление под названием «Проблема канадского путешественника» (CTP), которое получило свое название от разочарованных канадских автомобилистов, которые должны повернуть назад и найти новый маршрут, когда дорога впереди заблокирована снегом.
В CTP с каждым ребром графа связан вес, который показывает, сколько времени потребуется для прохождения этого пути, и вероятность того, насколько вероятно, что его можно будет пройти. Целью CTP является минимизация времени в пути до пункта назначения.
Исследователи сосредоточились на том, как автоматически генерировать график CTP, который эффективно представляет неопределенную среду.
«Если мы ориентируемся в окружающей среде, возможно, у нас есть некоторая информация, поэтому мы не просто идем вслепую. Хотя это не подробный навигационный план, он дает нам представление о том, с чем мы работаем. Суть этой работы — попытаться отразить это на графике CTP», — добавляет Курц.
Их алгоритм предполагает, что эта частичная информация — например, спутниковое изображение — может быть разделена на определенные области (одной областью может быть озеро, другой — открытое поле и т. д.).
Каждая область имеет вероятность того, что робот сможет пересечь ее. Например, неводный робот с большей вероятностью сможет передвигаться по полю, чем по озеру, поэтому вероятность появления поля будет выше.
Алгоритм использует эту информацию для построения исходного графа в открытом пространстве, намечая консервативный путь, который медленный, но определенно проходимый. Затем он использует метрику, разработанную командой, чтобы определить, какие ребра или кратчайшие пути через неопределенные регионы следует добавить в график, чтобы сократить общее время в пути.
Выбор ярлыков
Выбирая только те кратчайшие пути, которые могут быть пройдены, алгоритм предотвращает ненужное усложнение процесса планирования.
«Качество плана движения зависит от качества графика. Если в этом графе нет хороших путей, алгоритм не сможет дать вам хороший план», — объясняет Вейс.
После тестирования алгоритма в более чем 100 смоделированных экспериментах во все более сложных средах исследователи обнаружили, что он может постоянно превосходить базовые методы, не учитывающие вероятности. Они также протестировали его, используя воздушную карту кампуса Массачусетского технологического института, чтобы показать, что он может быть эффективным в реальных городских условиях.
В будущем они хотят усовершенствовать алгоритм, чтобы он мог работать более чем в двух измерениях, что позволит использовать его для решения сложных задач роботизированных манипуляций. Они также заинтересованы в изучении несоответствия между графиками CTP и реальной средой, которую эти графики представляют.
«Роботы, которые работают в реальном мире, страдают от неопределенности, будь то доступные данные датчиков, предварительные знания об окружающей среде или о том, как будут вести себя другие агенты. К сожалению, преодоление этих неопределенностей требует больших вычислительных затрат», — говорит Сет Хатчинсон, профессор и заведующий кафедрой робототехники KUKA в Школе интерактивных вычислений Технологического института Джорджии, который не участвовал в этом исследовании. «Эта работа решает эти проблемы, предлагая умную схему аппроксимации, которую можно использовать для эффективного расчета планов, толерантных к неопределенности».
Это исследование частично финансировалось исследовательскими лабораториями армии США в рамках Альянса совместных исследований распределенных интеллектуальных систем и технологий, а также стипендией выпускников Джозефа Т. Корсо и Лили Корсо.