Планирование покрытия: обход всего пола

Другая задача, чем попасть в пункт назначения

A* находит один маршрут к одной цели. Планировщик покрытия должен коснуться каждой достижимой клетки, и это полностью меняет задачу: нет цели, к которой нужно приблизиться, нет эвристики, а успех не является бинарным.

Вместо этого измеряется расстояние на один квадратный метр обработанного пола. При площади пола A и ширине инструмента w идеальный робот обрабатывает каждый квадрат один раз и не повторяет:

d_optimal = A / w

Комнате 20 m² с щёткой 250 mm нужно 80 m. Все значения ниже заданы относительно него, поэтому не зависят от размера комнаты.

Закон, управляющий обходом без карты

Робот, не знающий, где уже был, покрывает новую часть пола пропорционально доле пола, который ещё не покрыт. Это дифференциальное уравнение с одним ответом:

covered(d) ≈ 1 − e^(−d / d_optimal)

Снимите с него три точки — и форма всей задачи проявится:

Последние 9% стоят больше первых 90%. Это задача коллекционера купонов с прикреплённой щёткой, и это единственный факт, объясняющий каждый робот-пылесос, который вы когда-либо видели.

Что происходит на самом деле

Теория предполагает, что каждый метр попадает на независимо выбранный участок пола. Настоящий робот едет прямыми линиями, поэтому последовательные метры коррелированы: он постоянно заново обрабатывает участок, на котором уже стоит. При измерениях в пяти комнатах в симуляторе покрытия:

Три вещи в этой таблице важнее всего остального на странице.

В первой половине пола ничего не имеет значения. На 50% результаты всех трёх стратегий различаются не более чем на 20%. Робот без датчиков и памяти действительно не хуже планировщика на первой половине работы — именно поэтому дешёвый подход пригоден для массового применения и поэтому случайное наблюдение никогда не показывает разницу.

Случайный обход хуже собственной теории. 6.76× против предсказанных 4.61× на 99%, потому что отражение по прямой постоянно возвращается к только что обработанному полу. Считайте 1 − e^(−d) оптимистичной границей, а не оценкой.

Планировщик никогда не заканчивает. Он останавливается на 90.4% и дальше не меняет результат, и это не ошибка.

Почему планировщик оставляет десятую часть пола

Планировщик покрытия должен удерживать корпус робота подальше от каждой стены и каждой ножки стола, поэтому расширяет зону каждого препятствия на радиус робота плюс запас и планирует внутри оставшегося пространства. Всё, что оказалось снаружи, — это пол, до которого робот никогда не сможет доехать.

В измеренном прогоне 130 из 133 клеток, пропущенных планировщиком, находились в пределах двух клеток от стены или предмета мебели. Только три были открытым полом. Пропуски не разбросаны — они образуют кольцо вокруг каждого препятствия в комнате.

Это объясняет две особенности каждой коммерческой машины:

• Боковая щётка, выступающая за корпус. Щётка шире корпуса, с которым может столкнуться робот, поэтому она достаёт до пола, куда колёса никогда не доберутся.
• Проход вдоль стены. Это отдельный режим, выполняемый отдельно, потому что плановый обход не может предусмотреть его.

Случайное отражение рано или поздно достигает этих краёв — случайно, и это единственное, в чём оно лучше.

Выбор проходов

Для систематического обхода единственный реальный параметр — расстояние между проходами.

Разместите проходы точно на ширину щётки, и любая ошибка курса оставит между ними незачищенную полосу, которую больше никто не найдёт, потому что план считает этот пол обработанным. Перекрытие 10–20% закроет полосы ценой ровно этого процента расстояния.

Именно это перекрытие плюс расстояние переездов вокруг мебели дают планировщику 1.35×. Это не потеря, а цена плана, который работает с настоящим роботом.

Ещё два решения важнее, чем кажется:

• Проводите проходы вдоль длинной оси комнаты. Каждый поворот требует времени и не покрывает нового пола, поэтому уменьшение числа проходов вдвое уменьшает накладные расходы на повороты.
• Планируйте переходы между отрезками, а не езжайте между ними напрямую. Когда мебель разделяет проход на два отрезка, робот должен объехать вокруг. Планирование этого перехода как кратчайшего пути по свободному пространству — разница между планом и пожеланием.

Какие датчики нужны каждой стратегии

Вот настоящая причина существования всех трёх.

Случайному отражению нужен один бит. Произошло ли столкновение. Два датчика удара и генератор случайных чисел — это весь робот. Ни энкодеров, ни карты, ни локализации, и ничего, что могло бы дрейфовать.

Спирали нужно знать, как далеко она прошла от центра текущей спирали, то есть грубая одометрия — достаточно, чтобы увеличивать радиус, но недостаточно, чтобы замкнуть контур.

Плановому обходу нужно знать, где он находится. Прямые проходы, известные углы поворота и боковой шаг на ширину щётки — всё это предположения одометрии, а одометрия дрейфует. После десяти проходов проходы перестают быть параллельными. Поэтому коммерческие машины с планированием также несут гироскоп, потолочную камеру или маяк: планировщик дешёв, а предполагаемая им локализация обходится дороже.

Стратегия выбирается по бюджету датчиков, а не по элегантности алгоритма. Сначала постройте случайный вариант: он работает, занимает двадцать строк и даёт базовый уровень, который должен превзойти планировщик.

Сколько это стоит в минутах

Возьмём ту же комнату 20 m², щётку 250 mm и робота со скоростью 0.25 m/s:

Аккумулятор — это бюджет расстояния. Один час работы при 0.25 m/s даёт 900 m, чего с запасом хватает на одну комнату при случайном обходе, но не на три; именно это, а не какой-либо алгоритмический вывод, подтолкнуло рынок к роботам с картой.

Когда всё идёт не так

Запустите все три стратегии в одной комнате в симуляторе покрытия — перемещайте мебель во время работы, и числа изменятся вместе с ней. Затем постройте робота для покрытия помещения, который начинает со стратегии, не требующей датчиков, и добавляет их только там, где измерения показывают, что это окупается.