Читал вышепомянутый сайт, смотрел видео и размышлял. В соревнованиях помимо самого прохода через лабиринт имеет значение, как быстро робот находит кратчайший для себя путь. Мой робот, используя алгоритм Luke-Tremo пока не излазит весь лабиринт по два раза - не успокоится. В соревнованиях же micromouse это требует очень много времени (которое в тех соревнованиях ограничено, а в соревнованих в UK еще и процентуально добавлялось к времени чистого прохода). Так вот, можно ли на основании каких-то данных принять решение, что исследованной части лабиринта уже достаточно для нахождения кратчайшего пути или надо еще проверять неисследованные проходы?

Вот для примера упомянутый в предыдущем сообщении лабиринт (он немного отличается от того что в видео в двух местах). В видео робот проходит по алгоритму "левой руки", а мой робот проход до финиша выполнял по алгоритму "вперед-налево-вправо". Т.е.все перекрёстки проходил прямо, но если нет прямого хода, то влево и уж если и этой возможости нет,то только тогда вправо. Все остальные ветви робот долго и тщательно проверял на обратном пути. Хотя, в этом простом лабиринте можно было и не делать, так как найденный путь с учетом удалённых тупиков и так уже был кратчайшим (дурная особенность односвязных лабиринтов). Но если допустить, что лабиринт не односвязный (предположим, мы этого не знаем), то надо принять решение, искать еще или успокоиться. Я тут подумал, что в общем лабиринте из линий это определить невозможно. Надо иметь знание о границах как минимум. И скажем, "минимальный шаг" - знание, что перекрёстки могут находиться на расстоянии не меньше какой-то величины. Идеальный вариант, когда "шаг" фиксирован, как в лабиринтах для micromouse. Поэтому картинка вверху выполнена в таком стиле.
Ну вот тогда исходя из этих ограничений, можно начинать принимать решения. В одной из статей Питера Харрисона (похоже из владельцев того сайта), упоминается, что его роботы рассчитывают лабиринт постоянно в двух вариантах: "открытый лабиринт", когда все те стены что еще не обнаружены считаются что их нет вообще (кроме внешних стен, которые должны быть по условиям соревнований) и "закрытый лабиринт", когда все неопределённые места имеют стены. И по соотношению длин найденных кратчайших путей и принимается решение - решен лабиринт или нет. Вот, например, как выглядел бы открытый лабиринт для моего робота, когда он нашел выход:

Синяя линия показывает кратчайший путь, который в верхней части лабиринта совпадает с найденным уже путём. Поэтому, нет смысла искать все проходы и тупики, так как они на конечный результат не влияют. А вот в нижней части, маршрут пролегает уже через неизведанные ячейки. И не факт, что там можно проехать. Потому предполагается, что та часть лабиринта должна быть дополнительно исследована. Для себя я пока рассматриваю алгоритм - найти финиш, вычислить кратчайший путь исходя из открытости лабиринта и посетить ту ячейку, где путь проходит через неисследованные ячейки. Т.е.выбрать ближайшую неизведанную на пути, посетить её, пересчитать лабиринт и снова направиться к следующей ближайшей неизведанной ячейке. И так до тех пор, пока кратчайший путь не будет проходить по неизведанным ячейкам. Я тут помоделировал этот лабиринт, и, оказалось, что достаточно посетить максимум 3 ячейки сверх уже посещенных, чтобы однозначно утвердждать, что более короткий маршрут не может быть найден, поэтому остальные ячейки посещать нет необходимости.
Также у Питера Харрисона была презентация на соревнованиях Minos в 2009 году, где он представлял свой быстрый метод расчета лабиринта. (Смотрите заголовок:
Peter Harrison: Fast maze flooding techniques). Это алгоритм "заполнения", который очень удобен для такого "клетчатого" лабиринта. Вообще-то презентация алгоритма как раз перед его презентацией. Подумалось, что эту же технику можно применить и для алгоритма Дейкстры - надо только сделать сортировку очереди, чтобы сразу брать узел с минимальным расстоянием.
Об этом меня заставило задуматься еще одно видео, что нашел на
YouTube. Там роботы соревновались на вот таком лабиринте:

Когда я этот лабиринт подсунул своему роботу он нашел кратчайший путь, но я представляю, сколько времени потребовалось бы, чтобы он эту карту создал. Потому и встал вопрос об отказе от полного "сканирования" лабиринта.
Еще меня в этих видео заинтересовали роботы типа 3pi (маленькие и круглые - там было несколько модификаций). Вот такого робота мне хотелось бы сделать. Пошел на сайт pololu почитать про них. А оказывается, в ноябре был выпущен новый 3pi робот. Хоть и на "более мощном" микроконтроллере, но не для меня - и старый и новый - это восьмибитная ардуина. старая классическая:Atmel 328, а новая Atmel 32U4. Эх, был бы там какой ST или Cypress, или какой другой ARM - купил бы. Хотя, я поизучал их конструкции. С сенсорами линии там плохо - 3 центральных сенсора и 2 боковых. И стоят они - в старом на расстоянии 10мм от поверхности, у нового - 20мм! Не, наверное, линию (вернее позицию линии) они разглядеть могут. Но они могут это сделать так же, как и я без очков. Т.е. видят какую-то муть и разглядеть там одна линия или 2 они уже не могут. У нового робота сразу на борту есть таходатчики двигателей и акселерометр. На новый год были скидки у Pololu, и я чуть было шасси не купил, с мыслью сделать свою плату. Но решил пока погодить.
Посмотрел еще раз видео - они тоже при торможении "клюют носом".
Немного подрессировал своего робота. Научил его отличать красный от зеленого на той бумаге, что мне тогда напечатали. Я сделал перед передачей на вычисление Hue проход значений через "аттенюатор" - т.е. каждое значение можно чуть усилить или ослабить. А так как я к этим переменным имею доступ через командный интерфейс, я мог просто введя команду:
сразу видеть результат. Так что я "слегка" задавив уровень сигнала красного канала сделал достаточно четкое различие - зелёное поле - зелёное, красное поле - красное, белый лист - белый, а цвет моей трассы - желтый. Если робота приподнять - черный. Меня устраивает.
А тут на меня снизошло (вообще-то снизошло полтора месяц назад), что так как я командами могу прочитать все переменные, то я и результат вывода могу сохранить в виде текста. Т.е. для запоминания конфигурации мне не нужно делать копию памяти робота. Всё это доступно в текстовом виде, а путём небольшой модификации (сзади надо добавить только "swap !") получить командный файл, который восстановит мне все конфигурационные переменные в заданное состояние:
Код: Выделить всё
Threshold 800 swap !
MAXspeed 16000 swap !
MINspeed 10000 swap !
MAXmotor 16000 swap !
TurnSpeed 6000 swap !
Accelerat 100 swap !
K*error 10 swap !
K*de/dt 120 swap !
Kintegral 0 swap !
MotorKprop 135 swap !
MotorKint 256 swap !
OnWay 100 swap !
итд.
Вот это фрагмент конфигурации сделанный 31 декабря.
Нашел куда прикрепить датчик цвета. Первоначально, я его держал впереди, так, чтобы, когда сенсор линии обнаружит тупик - сенсор цвета уже находился над цветным полем. Типа, для того чтобы выяснить цвет до выполнения маневра. Но какой в тупике может быть манёвр, кроме как развернуться? Ну да - если поле красное разворачиваться не нужно - нужно ехать вперёд. Но тут я решил, так как я не могу найти спереди места для датчика цвета - поставлю я его сзади и цвет буду проверять после разворота. А если цвет поля (о ужас!) окажется красным, то я на финишное поле могу и задом заехать. Но вообще, это только в том случае, если я не использую возможность изучить лабиринт. Если же я изучаю лабиринт и функция вычисления кратчайшего пути создаёт маршрут - то тогда я цвет не проверяю вообще, а просто по окончании маршрута считаю, что впереди финиш и проезжаю вперед.
Хотя всё это мечты. 2 соревнования уже пролетело, третье, 30 января - тоже, пролетит. Чую, этот коронавирус не даст покоя до лета.
А люди посмотрят и скажут: "Собаки летят. Вот и осень."