Дизайн лабиринта
Оригинальный лабиринт: Лабиринт
Лабиринт:
- Структура Крита:Лабиринт: без разветвления и обхода
- структура графа: односвязная или многосвязная
Наш робот может находить пути в просто связанных лабиринтах, что означает отсутствие петель и связность. Существует множество алгоритмов решения лабиринтов, тесно связанных с теорией графов.
- Путешественник, не знакомый с лабиринтом, который является предметом нашего исследования. Существует три типичных стратегии: случайная мышь, поиск в глубину, следование по стене.
- Супервайзер может сразу увидеть весь лабиринт: эта задача намного проще, и существуют различные эффективные алгоритмы: алгоритм поиска кратчайшего пути, поиск в ширину или поиск в глубину.
Исследование лабиринта в роли путешественника
Случайная мышь
тривиальный метод
- продолжать движение в текущем направлении, пока не будет достигнуто препятствие
- сделать случайный выбор доступных направлений и продолжить
Последователь стены
самый известный алгоритм обхода лабиринта
- правило левого направления
- правило правильного направления
Почему слежение за стеной работает?
- Лабиринты, не содержащие никаких петель, называются "односвязными" или "идеальными" лабиринтами и эквивалентны дереву в теории графов.
- внутренняя стена: ветвь, вытянутая из внешней стены
- Если стены соединены, то они могут деформироваться в петлю или круг.
https://www.youtube.com/watch?v=k1tSK5V1pds
если лабиринт не просто подключен?
(т. е. если начальная или конечная точки находятся в центре структуры, окруженной проходными петлями, или пути пересекаются друг с другом и под ним и такие части пути решения окружены проходными петлями), этот метод не достигнет цели.
Мы можем установить предпочтительное направление
Если текущее направление совпадает с предпочтительным направлением, двигайтесь вперед, а не вдоль стены.
Однако при входе в лабиринт в форме буквы G он попадет в ловушку.
#### Мы также можем установить значение «Сумма сделанных ходов».
- при повороте направо уменьшать
- при повороте налево уменьшать
- продолжай идти вперед
- задать предпочтительное направление
- если текущее направление совпадает с предпочтительным направлением
- если «сумма сделанных ходов» равна 0:
- еще
2. Дизайн робота
Прототип робота
Мы прикрепляем датчик компаса к исходному прототипу электронной шайбы. Прототип электронной шайбы с датчиками:
- дифференциал_Колеса и энкодер
- камера
- светодиоды
- датчик расстояния: ИК-датчик
Контроллер
- случайный контроллер
- следящий за стеной контроллер
- контролер залога
Модули контроллера:
- стена изменена
- порог
- уклон назад
- решить, в каком направлении двигаться дальше
- Поверните налево
- Поверните направо
3. Демонстрация производительности
Видео-демо: пожалуйста, убедитесь, что вы можете свободно посещать YouTube.
Ознакомьтесь с нашим исходным кодом здесь: https://github.com/haoransh/Maze-Robot-on-Webots!