Лекция
Сразу хочу сказать, что здесь никакой воды про поиск выхода из лабиринта, и только нужная информация. Для того чтобы лучше понимать что такое поиск выхода из лабиринта , настоятельно рекомендую прочитать все из категории Робототехника.
Правило правой руки. Элементы лабиринта. Построение карты лабиринта.
Вспомните веселую историю, рассказанную английским писателем Джеромом К. Джеромом в книге “Трое в лодке (не считая собаки)” (если не читали, то обязательно прочитайте — это в главе 6). Сколько людей смеялось над чудаком Гаррисом, попавшим в Хемптон-Кортский лабиринт!
— Мы только зайдем сюда, чтобы ты мог сказать, что побывал в лабиринте, но это совсем не сложно. Даже нелепо называть его лабиринтом. Мы походим здесь минут десять, а потом отправимся завтракать, — уговаривал Гаррис своего родственника.
Но увы! Он не только заблудился сам, но и запутал людей, которых взялся избавить от мучительного блуждания по лабиринту. За ним следовало по крайней мере человек двадцать и даже одна женщина с ребенком, безуспешно искавшая выход из лабиринта все утро.
Следуя своей тактике, Гаррис все время поворачивал направо. Ему казалось, что вот-вот он выберется из лабиринта. Но время шло, и... вся компания во главе с Гаррисом вернулась к тому месту, где они уже были. Половинка булочки, брошенная ребенком и замеченная родственником Гарриса семь минут тому назад, с несомненностью указывала место их недавнего пребывания.
Тогда Гаррис предложил вернуться назад и начать все снова. Предложение начать снова особого энтузиазма не вызвало, но все согласились вернуться.
Процессия повернула обратно и потянулась за Гаррисом в противоположном направлении, но через десять минут вся компания снова очутилась в центре лабиринта. Такой же неудачей закончились и последующие попытки. В какую бы сторону они ни сворачивали, все пути приводили их в центр. Это стало повторяться с такой правильностью, что некоторые просто оставались на месте и ждали, пока остальные прогуляются и вернутся к ним.
Наконец отчаявшиеся любители лабиринта призвали на помощь сторожа, который и вывел их на “свободу”.
Бедному Гаррису не пришлось бы блуждать и мучить людей, если бы он знал алгоритм поиска путей в лабиринте. Таких алгоритмов существует несколько. Один из них связан с древнегреческим мифом о легендарном герое Тезее, который отважился проникнуть в лабиринт для того, чтобы разыскать в нем чудовищного Минотавра и убить его. Ему помогла выбраться из лабиринта Ариадна, давшая Тезею клубок ниток, один конец которых держала она сама. По мере углубления Тезея в лабиринт клубок разматывался; наматывая потом нитки, Тезей благополучно вернулся к выходу.
Представим себе лабиринт в виде конечной системы площадок, от которых расходятся коридоры, причем каждый коридор соединяет две площадки (такие площадки будем называть смежными), но не исключается существование таких площадок, из которых можно пройти только в один коридор (такие площадки будем называть тупиками). Геометрически лабиринт можно представить в виде системы точек А, В, С, … (изображающих площадки) и совокупности отрезковАВ, ВС, … (изображающих коридоры), соединяющих некоторые пары этих точек (рис. 1).
Рис. 1
Будем говорить, что площадка Y достижима из площадки X, если существует путь, ведущий от X к Y через промежуточные коридоры и площадки. Точнее, это означает, что либо X и Y — смежные площадки, либо существует последовательность площадок Х1, Х2, Х3, ..., Хn, таких, что пары площадок Х иХ1, Х1 и Х2, Х2 и Х3, …, Хn и Y смежны. Например, на приведенном рисунке площадка Н достижима из тупика А посредством пути АВ, ВС, СD, DЕ, ЕF, FD, DН, в то время как площадка K не достижима из А. Вместе с тем, если Y вообще достижима из X, то она достижима и посредством простого пути, т.е. такого пути, в котором каждая площадка (а тем более и каждый коридор) проходится лишь один раз. В предыдущем примере путь не был простым, но, срезав петлюDЕ, ЕF, FD, мы получаем простой путь АВ, ВС, СD, DН.
Предполагается, что Минотавр находится на одной из площадок лабиринта (обозначим ее М), а Тезей, отправляясь на его поиски с площадки А, на которой его ждет Ариадна, должен решить следующую задачу: требуется выяснить, достижима ли М из А или нет1. Если достижима, то нужно добраться до нее по какому бы то ни было пути, но вернуться к Ариадне нужно уже по простому пути. Если же М недостижима, то вернуться к Ариадне.
Различных лабиринтов может быть бесчисленное множество, а взаимное расположение в данном лабиринте площадок А и М также можно варьировать. Поскольку Тезею заранее ничего не известно об устройстве данного лабиринта и о местонахождении в нем Минотавра, то решение поставленной задачи мыслится в виде общего метода поисков, пригодного при любом лабиринте и при любом расположении в нем площадок А и М. Иными словами, решение мыслится в виде алгоритма, решающего любую из задач данного типа (именно в этом, как известно, заключается такое свойство алгоритма, как массовость).
Алгоритм поиска. Для построения такого алгоритма мы рассмотрим один специальный метод поисков. На любой стадии процесса поиска в соответствии с этим методом приходится различать коридоры:
1) еще ни разу не пройденные Тезеем (условно — зеленые);
2) пройденные один раз (желтые);
3) пройденные дважды (красные).
Далее, находясь на какой-либо площадке, Тезей может попасть на одну из смежных площадок посредством одного из следующих двух ходов:
1. Разматывание нити. Прохождение от данной площадки по любому зеленому коридору до смежной площадки. При этом нить Ариадны разматывается вдоль этого коридора, который после прохождения уже считается желтым.
2. Наматывание нити. Возвращение от данной площадки по последнему пройденному желтому коридору до смежной площадки. При этом нить Ариадны, ранее размотанная вдоль этого коридора, наматывается обратно, а этот коридор уже объявляется красным.
Предполагается, что Тезей делает какие-то пометки, позволяющие ему впоследствии отличать зеленые коридоры от зеленых; желтые различимы тем, что по ним протянута нить Ариадны2. Выбор того или иного хода зависит от обстановки, наблюдаемой Тезеем на той площадке, на которой он находится в данный момент; эту обстановку можно охарактеризовать одним или несколькими из следующих признаков:
1. Об этом говорит сайт https://intellect.icu . Минотавр. На данной площадке обнаружен Минотавр.
2. Петля. Через данную площадку уже протянута нить Ариадны; иными словами, от площадки расходятся по крайней мере два желтых коридора.
3. Зеленая улица. На данной площадке есть выход по крайней мере в один зеленый коридор.
4. Ариадна. На данной площадке находится Ариадна.
5. Пятый случай. Отсутствие всех предыдущих признаков.
Наш метод поиска может быть теперь задан следующей схемой (см. табл. 1):
Таблица 1
Находясь на какой-нибудь площадке, Тезей делает очередной ход так: он проверяет по порядку номеров в левом столбце схемы, какой из перечисленных признаков имеет место; обнаружив первый такой признак, он (уже не проверяя остальные признаки) делает соответствующий ход (или остановку) из правого столбца. Такие ходы делаются до тех пор, пока не наступит остановка.
Пригодность предложенного метода непосредственно вытекает из следующих трех утверждений:
1. При любом взаимном расположении А и М в лабиринте после конечного числа ходов обязательно наступит остановка либо на площадке Минотавра, либо на площадке Ариадны.
2. Если остановка наступила на площадке Минотавра, то Минотавр достижим. Более того, в этом случае нить Ариадны оказывается протянутой по простому пути, ведущему от А до М; наматывая нить, Тезей может теперь вернуться по этому пути к Ариадне.
3. Если остановка наступила на площадке Ариадны, то Минотавр недостижим.
С доказательством этих утверждений можно познакомиться, например, в .
А мы покажем на двух примерах, как работает предложенный метод.
Пример 1. Пусть с площадки А лабиринта (см. рис. 1) начинается поиск Минотавра, который находится в F. Процесс поиска в соответствии с нашим методом удобно изобразить посредством схемы, представленной в табл. 2 (из-за свободы в выборе зеленого коридора — это лишь одна из возможных схем).
Мы видим, что в данном случае Минотавр достижим. Выделив в предпоследнем столбце те из коридоров, которые остались желтыми (в соответствии с показаниями последнего столбца), получим следующий простой путь, ведущий от А к F: АВСDF.
Пример 2. Если же поиск начинается с площадки К, то процесс поиска можно отразить в схеме, представленной в табл. 3.
Мы видим, что в этом случае Минотавр недостижим.
Заметим, что описанный алгоритм не обладает свойством определенности — с какой-то площадки могут оказаться выходы в несколько зеленых коридоров, а наше предписание не указывает, какой из них выбрать, точнее — оно допускает произвольный выбор одного из них. Чтобы это свойство соблюдалось, необходимо регламентировать, как должен проводиться выбор очередного проверяемого коридора в таких ситуациях.
Таблица 2
Таблица 3
Составьте схему выхода из лабиринта (с площадки 1 на площадку 10 — см. рис. 2), используя описанный в этой статье алгоритм:
При наличии на площадке выходов в несколько зеленых коридоров перемещение по ним должно идти “по часовой стрелке”.
Схемы, пожалуйста, оформите в виде таблиц, аналогичных табл. 2 и табл. 3.
Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Хотя у этого правила и есть один недостаток, но о нем мы поговорим позже.
Попробуем описать робота, действующего в соответствии с правилом "правой руки".
В начале своей работы робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду.
После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом "правой руки".
Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа.
Если прохода нет - впереди стена - робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.
Блок-схема алгоритма для робота, работающего по правилу "правой руки", представлена на рисунке.
Рис Блок-схема алгоритма для робота, работающего по правилу
Попробуем проверить работу данного алгоритма и напишем для него программу. Для этой цели обратимся к среде программирования GameLogo. Эта среда является удобным средством для моделирования различных алгоритмов, связанных с управлением роботами. В ней есть исполнитель черепаха, который по своей сути является не чем иным, как самым настоящим роботом. Черепаха располагает очень удобным набором команд - вперед, направо, налево, назад. Кроме того, в центре черепахи есть датчик, принимающий значение от 0 до 100, в зависимости от тона поверхности, на которой она находится.
Диалект языка Лого, который мы будем использовать, очень прост и похож на Basic. Познакомиться с командами языка можно здесь. А бесплатно скачать среду программирования GameLogo - здесь. Размер дистрибутива невелик - всего 1 Mb.
В архиве с GameLogo есть фоны с лабиринтами, одним из которых мы и воспользуемся.
Файл maze1.gif
переменная флагВ самом начале программы дадим команду черепахе, чтобы она подняла перо (по умолчанию черепаха оставляет после себя след).
Размер поля - 800 на 600 точек. Исходное положение для черепахи находится в месте с координатами 115, 545 (белый квадрат).
Цвет дорожек лабиринта - светлый, на них датчик будет принимать значения больше 50. Цвет стен лабиринта - темный, значение датчика будет меньше 50. Выход из лабиринта представлен черным квадратом, значение датчика над которым будет равно 0.
Объявим переменную флаг, с помощью которой будем контролировать, достигнут ли выход из лабиринта.
Напишем программу и запустим ее с помощью большой красной кнопки с надписью "Выполнить".
фон = maze1.gif
поднять перо
место 115, 545
' поиск первой стены
повторять пока датчик > 50 {
вперед 12
}
' правило правой руки
повторять пока флаг = 0 {
направо 90
вперед 12
если датчик = 0 то
флаг = 1
иначе
если датчик < 50 то
назад 12
налево 90
вперед 12
если датчик < 50 то
назад 12
налево 90
конец условия
конец условия
конец условия
}
пиши "цель достигнута"
Если известно, что у лабиринта нет отдельно стоящих стенок, то есть нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт называют односвязным и его всегда можно обойти полностью, применив правило "одной руки".
Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило "одной руки", не всегда можно пройти все коридоры и тупики. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными. При этом многосвязные лабиринты можно разделить на две группы: без "петли" вокруг цели (замкнутый маршрут не проходит вокруг цели) и с замкнутой "петлей" вокруг цели (цель можно обойти по замкнутому маршруту).
Робот для прохождения лабиринта на базе ATmega8
(соревнования Micromouse competition).
Зная алгоритм Тремо, можно скорректировать поведение легендарного Тесея. Вдохновленный подарком любимой Ариадны, он уверенно идет по лабиринту. Вдруг перед ним возникает ход, по которому уже протянута нить... Что делать? Ни в коем случае не пересекать ее, а вернуться по уже известному пути, сдваивая нить, пока не найдется еще один непройденный ход.В многосвязных лабиринтах второй группы правило "одной руки" не работает и, применяя его, достичь цели невозможно. Но и эти лабиринты можно пройти, полагаясь на точный алгоритм.
Решение задачи о таких лабиринтах принадлежит сравнительно позднему времени, и начало ему положено Леонардом Эйлером. Эйлер не без оснований полагал, что выход из любого лабиринта может быть найден, и притом сравнительно простым путем.
Универсальный алгоритм прохождения любых лабиринтов был описан только через столетие в книге французского математика Э. Люка "Recreations matematiques", изданной в 1882 году. Интересно, что Люка при описании алгоритма указал на первенство другого французского математика М. Тремо. Таким образом, алгоритм стал известен как алгоритм Люка-Тремо.
Тремо предлагает следующие правила: выйдя из любой точки лабиринта, надо сделать отметку на его стене (крест) и двигаться в произвольном направлении до тупика или перекрестка; в первом случае вернуться назад, поставить второй крест, свидетельствующий, что путь пройден дважды - туда и назад, и идти в направлении, не пройденном ни разу, или пройденном один раз; во втором - идти по произвольному направлению, отмечая каждый перекресток на входе и на выходе одним крестом; если на перекресте один крест уже имеется, то следует идти новым путем, если нет - то пройденным путем, отметив его вторым крестом.
Клод Шеннон (Claude Elwood Shannon)
Применив вариант алгоритма Тремо, отец теории информации Клод Шеннон (Claude Elwood Shannon) построил одного из первых самообучающихся роботов. Шеннон дал ему звучное имя "Тесей", но в истории "Тесей" стал больше известен как "мышь" Шеннона. "Мышь" сначала обследовала весь лабиринт, а затем (во второй раз) проходила весь путь значительно быстрее, избегая участков, пройденных дважды.
Лабиринт на соревнованиях Micromouse competition.
В наши дни роботы, проходящие лабиринт, являются участниками одного из самых интересных состязаний думающих машинок, которое проходит в нескольких странах мира. Эти соревнования носят общее название Micromouse competition и по своим техническим новациям относятся к лидерам робототехнического спорта.
На первой Российской Олимпиаде Роботов проводились соревнования, целью которых было прохождение своеобразного лабиринта: за наиболее короткое время, двигаясь через "открытые двери" в стенках, робот должен был добраться от места старта до места финиша. Контролировать свое движение робот мог по черным линиям, нанесенным на пол лабиринта.
генерация лабиринта , прохождение лабиринта ,
А как ты думаешь, при улучшении поиск выхода из лабиринта, будет лучше нам? Надеюсь, что теперь ты понял что такое поиск выхода из лабиринта и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Робототехника
Комментарии
Оставить комментарий
Робототехника
Термины: Робототехника