Для этого вопроса предположим, что следующие вещи неизвестны:
- Размер и форма комнаты
- Расположение робота
- Наличие каких-либо препятствий
Также предположим, что следующие вещи являются постоянными:
- Размер и форма комнаты
- Количество, форма и расположение всех (если есть) препятствий
И предположим, что робот обладает следующими свойствами:
- Он может двигаться только вперед с приращением абсолютных единиц и поворачиваться в градусах. Также перемещающаяся операция вернет true, если она прошла успешно, или false, если она не смогла двигаться из-за препятствия.
- Достаточно неограниченный источник энергии (скажем, это робот, работающий на солнечной энергии, размещенный на космической станции, которая постоянно смотрит на солнце без потолка)
- Каждое движение и поворот выполняются с абсолютной точностью каждый раз (не беспокойтесь о недостоверных данных)
Наконец, рассмотрите следующие свойства среды робота:
- Находясь на космической станции без потолка, комната находится в безопасном, но очень близком расстоянии от проходящих комет, поэтому пыль (и лед) постоянно засоряют окружающую среду.
Мне задали гораздо более простую версию этого вопроса (комната - это прямоугольник, и нет никаких препятствий, как бы вы переместились через него, гарантируя, что вы могли бы пройтись по каждой части хотя бы один раз), и после этого я начал задаваться вопросом, как бы вы подошли к этому, если бы вы могли не гарантирует форму или наличие препятствий. Я начал смотреть на это с помощью алгоритма Дейкстры , но мне очень интересно услышать, как другие к этому подходят (или если есть хорошо принятый ответ на это? (Как Roomba делает это?)
источник
Ответы:
Насколько я знаю, эта проблема не была "решена".
Формально это проблема онлайн-покрытия. Покрытие, потому что мы должны покрывать каждую точку на полу, и онлайн, потому что у нас нет автономного доступа к карте. Если вас интересуют самые последние результаты, я предлагаю вам поискать « алгоритмы роботизированного онлайн-покрытия », возможно, в google scholar (есть много и много отличных результатов). В дополнение к очень красочному (пере) посту @ embedded.kyle я добавлю некоторые детали (я также постараюсь быстро найти несколько простых результатов):
Dijkstra's даст вам путь, но не обязательно освещение. Например, как вы указываете Дейкстре, что вы должны посещать каждую точку на графике, а не посещать одну точку как можно быстрее? Вы можете пробежать все пары по кратчайшим путям, но в чем смысл? У вас нет карты.
Подобные алгоритмы онлайн часто называют алгоритмами «ошибок», потому что они имеют тенденцию быть похожими на ошибку, блуждающую по области, сталкивающуюся с чем-то, а затем немного блуждающую вокруг.
Без препятствий и прямоугольной комнаты, и при условии, что вы начинаете на границе , путь бустрофедона (путь вола) является оптимальным.
Забавно, что фермеры делали это всегда, верно? http://en.wikipedia.org/wiki/Boustrophedon . Это можно распространить на комнаты с препятствиями, найдя примерно прямоугольную область, свободную от препятствий. Хоуи Чосет немного поработал над этим .
Самая большая проблема у вас нет карты. Без карты вы ограничены простыми действиями, такими как следование по периметру и движение по пути (как упомянуто по спирали). Итак, существуют некоторые роботы, которые на самом деле строят карту во время очистки, разбивают намеченную область на фигуры, а затем покрывают каждую фигуру, чтобы обеспечить покрытие. Смотрите: http://mintcleaner.com/
источник
Roomba начинается по спирали, пока не натолкнется на что-то, а затем развернется по периметру. Тогда это просто подпрыгивает. Roomba, являющийся стандартом де-факто в бытовых роботизированных пылесосах, думаю, вы могли бы назвать это «принятым решением». Но из личного опыта (у меня есть два), безусловно, есть место для улучшения.
Из того, как работает материал :
Из интервью с Нэнси Дюссо Смит, вице-президентом по маркетинговым коммуникациям в iRobot:
Некоторые снимки Roombas со светодиодами на длинных выдержках иллюстрируют, как это работает на практике:
источник
Neato использует организованный подход. Используя SLAM и бамперы, он отображает «текущую» комнату, сначала периметр, а затем применяет некоторый алгоритм для очистки максимально эффективно. У меня никогда не было Roomba, но, учитывая то, что я прочитал об ее алгоритме, я бы никогда не переключился на neato.
Лазерный дальномер в автомате часто используется для робототехники, поскольку он является экономически эффективным датчиком для алгоритмов SLAM.
Если бы мне дали вашу задачу, сначала я бы нашел подходящую реализацию SLAM , основываясь на имеющемся у меня оборудовании.
Тогда я бы использовал алгоритм планирования движения ОСТРОВА с ЧПУ . По моему опыту, они, как правило, очень эффективно покрывают произвольную область с наименьшим количеством движения.
источник
Первое, что вам нужно установить, это цель робота - не совсем понятно из вашего вопроса. Есть две основные задачи, которые должен выполнить ваш робот: определить форму очищаемой области, а затем очистить ее.
Но постоянно ли количество грязи? Постоянно ли добавляется грязь? Ваша цель - минимизировать среднее время, в течение которого грязь остается на полу, или среднее время? Является ли цель сохранить пол в равной степени чистым? Или это просто один раз, как можно быстрее? Существуют ли модели накопления грязи, которые вы можете измерить и использовать в своих интересах для достижения своей цели?
Ответ на эти вопросы поможет определить, какой алгоритм вы выберете. В случае робота Roomba, возможно, нет смысла изучать точную планировку комнаты, потому что мебель (например, стулья вокруг стола), люди и другие препятствия перемещаются очень часто. Тем не менее, в вашем случае, возможно, было бы лучше исследовать пространство для построения полной карты (некоторая комбинация схемы газонокосилки с поиском краев), а затем использовать эту карту для вычисления кратчайшего пути через пространство (термин «охват», и есть несколько способов сделать это, например , алгоритм связующего дерева ).
Еще одна вещь, о которой вам нужно беспокоиться, это как дискретизировать пространство, в котором вы находитесь. Поскольку вы можете двигаться в любом направлении - даже с целочисленными величинами в градусах и целыми единицами расстояния - ваши позиции X и Y могут иметь дробные значения. Вам нужно решить, как представлять препятствия на этой карте, не увеличивая ее до бесконечного числа точек данных.
источник
Я не уверен, что вам все еще это нужно, но для тех, кто случайно наткнулся на эту тему, я сделал одну простую версию алгоритма.
По сути, он пытается построить карту области, пока очищается, и использует карту, чтобы найти ближайший неучтенный узел (часть комнаты). Если он не может его найти, это означает, что помещение убрано (или неочищенные части недоступны для робота).
Он может быть медленнее, чем другой алгоритм, но он может гарантировать покрытие независимо от начальной позиции, направления и препятствий.
https://github.com/dungba88/cleaner_robot
ОБНОВЛЕНИЕ: я сделал демо здесь и сравниваю его с возвратом DFS. Поэтому, хотя мой алгоритм O (N ^ 2), он гораздо более оптимизирован с точки зрения количества ходов и ходов.
http://jenova.dungba.org/cleaner/showdown
источник
Глядя на более простую проблему, которую вам задали, - прямоугольную комнату, в которой нет препятствий и уберите каждую часть хотя бы один раз.
Решение состоит в том, чтобы найти угол комнаты, и поиск угла не будет большой проблемой. Как только это будет достигнуто, просто следуйте по спиральной дорожке к центру комнаты.
источник