Симулятор планирования пути покрытия для роботов-пылесосов

Управление

Стратегия переключает между тремя вариантами. Комната перестраивается, а запуск немедленно начинается заново, потому что показатель покрытия имеет смысл только рядом с комнатой, в которой он измерен.

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

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

Теория

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

Единственная честная мерка — расстояние, которое понадобилось бы идеальному роботу. Для пола площадью A и щётки шириной w проход по каждой клетке ровно один раз без повторов требует:

d_optimal = A / w

Всё, что показывает лаборатория, кратно этому числу. Стратегия со значением 1.2× тратит 20% времени на повторное прохождение уже обработанного пола; стратегия со значением 8× — семь восьмых времени.

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

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

Именно это пунктирная кривая на графике. Снимите с неё три точки: 63% пола после одного идеального расстояния, 90% после 2.3 и 99% после 4.6. Последняя десятая часть комнаты стоит вдвое больше, чем первые три четверти, — задача о сборщике купонов, теперь со щёткой.

Систематическое покрытие линейно, поэтому оно заканчивается на 1× плюс накладные расходы от расстояния между рядами и поворотов. В этой лаборатории они составляют около 35%.

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

Алгоритм

Случайный отскок. Ехать прямо. При касании выбрать случайное новое направление и проверить, что оно свободно. Вот и всё, для чего нужен один бит данных датчика и никакой памяти.

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

Плановый змеевидный проход. Три шага, и второй пропускают чаще всего:

1. Расширить. Увеличить каждый объект на радиус робота и запас безопасности. Оставшаяся область — место, где может находиться центр робота.
2. Разрезать. Пройти раздутую карту рядами с расстоянием в одну ширину щётки. Каждый ряд становится одним или несколькими свободными отрезками.
3. Соединить. Обойти отрезки в змеевидном порядке и строить маршрут между соседними отрезками по кратчайшему пути через свободное пространство, чтобы робот объезжал вокруг дивана, а не въезжал в него.

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

Исходный код

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

// Random-bounce coverage. Two bump switches, no map, no encoders.
const uint8_t BUMP_L = 2, BUMP_R = 3;
const uint16_t CRUISE = 170;      // PWM
unsigned long turnUntil = 0;
int turnDir = 1;

void loop() {
  bool left  = digitalRead(BUMP_L) == LOW;   // switches are active-low with pull-ups
  bool right = digitalRead(BUMP_R) == LOW;

  if (millis() < turnUntil) {                 // still executing a bounce
    drive(turnDir * CRUISE, -turnDir * CRUISE);
    return;
  }

  if (left || right) {
    // Back off first — turning while wedged against a chair leg does nothing.
    reverseFor(320);
    // A random turn between 90 and 270 degrees. The randomness is what stops the
    // robot tracing the same closed loop around the room forever.
    turnDir = right ? -1 : 1;
    turnUntil = millis() + random(420, 1250);
    return;
  }

  drive(CRUISE, CRUISE);
}

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

Плановому проходу нужен описанный выше проход inflate-slice-join, а также одометрия, достаточно точная, чтобы удерживать прямой ряд; это уже другой класс роботов. Сначала создайте прототип здесь, где положение точно по построению, а затем решайте, сможет ли ваше оборудование его обеспечить.

Допущения и отличия от реального оборудования

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

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

Разрыв между стратегиями сохраняется несмотря на всё это. Если планировщик здесь обыгрывает случайный отскок в 3×, на настоящем оборудовании он, возможно, обыграет его примерно в 2×; порядок не изменится.

Схема соединений

Датчики здесь чисто разделяются на три задачи, и обязательна только первая.

Касание. Два микровыключателя на пружинном переднем бампере, подключённые с активным низким уровнем к выводам с поддержкой прерываний, со включёнными внутренними подтягивающими резисторами. Именно эти датчики делают возможным случайный отскок, и именно они выходят из строя последними.

Обрыв. Датчики отражения вниз в передних углах, считываемые на каждом проходе цикла. За покрытием робот посещает все места, включая начало лестничного марша; арифметика расстояния, которое робот проходит после края до остановки, разобрана здесь.

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

Описание сборки стратегий покрытия см. в проекте робота для покрытия комнаты; о реактивном слое под всеми ними рассказывает симулятор обхода препятствий, где рассматриваются пороги остановки и сканирование.