Дизайн лабиринта

Оригинальный лабиринт: Лабиринт

Лабиринт:

  • Структура Крита:Лабиринт: без разветвления и обхода
  • структура графа: односвязная или многосвязная

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

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

Исследование лабиринта в роли путешественника

Случайная мышь

тривиальный метод

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

Последователь стены

самый известный алгоритм обхода лабиринта

  • правило левого направления
  • правило правильного направления

Почему слежение за стеной работает?

  • Лабиринты, не содержащие никаких петель, называются "односвязными" или "идеальными" лабиринтами и эквивалентны дереву в теории графов.
  • внутренняя стена: ветвь, вытянутая из внешней стены
  • Если стены соединены, то они могут деформироваться в петлю или круг.

https://www.youtube.com/watch?v=k1tSK5V1pds

если лабиринт не просто подключен?

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

Мы можем установить предпочтительное направление

Если текущее направление совпадает с предпочтительным направлением, двигайтесь вперед, а не вдоль стены.

Однако при входе в лабиринт в форме буквы G он попадет в ловушку.

#### Мы также можем установить значение «Сумма сделанных ходов».

  • при повороте направо уменьшать
  • при повороте налево уменьшать
  • продолжай идти вперед
  • задать предпочтительное направление
  • если текущее направление совпадает с предпочтительным направлением
  • если «сумма сделанных ходов» равна 0:
  • еще

2. Дизайн робота

Прототип робота

Мы прикрепляем датчик компаса к исходному прототипу электронной шайбы. Прототип электронной шайбы с датчиками:

  • дифференциал_Колеса и энкодер
  • камера
  • светодиоды
  • датчик расстояния: ИК-датчик

Контроллер

  • случайный контроллер
  • следящий за стеной контроллер
  • контролер залога

Модули контроллера:

  • стена изменена
  • порог
  • уклон назад
  • решить, в каком направлении двигаться дальше
  • Поверните налево
  • Поверните направо

3. Демонстрация производительности

Видео-демо: пожалуйста, убедитесь, что вы можете свободно посещать YouTube.

Ознакомьтесь с нашим исходным кодом здесь: https://github.com/haoransh/Maze-Robot-on-Webots!