Бегущий в лабиринте

Бегущий в лабиринте

В двух предыдущих постах я описывал, как решал первую задачу из отборочного этапа хакатона МТС True Tech Champ.

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

► Визуализация лабиринта

Первое, что я сделал, это создал себе программу для визуализации данных, как их видит робот. Напомню, что в этом состязании у робота нет знания о структуре лабиринта. Всё, что он знает - это то, что видит перед собой с помощью лидара. Лидар это лазер, который вращается и сообщает роботу дистанцию до препятствий, находящихся под разным углом. Так вот, с помощью библиотеки RayLib я сделал визуализацию, которая отображает известную роботу часть лабиринта. И по ходу движения робот этот лабиринт дорисовывает, ощупывая стены лучами лидара.

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

► Коррекция положения

За счет того, что робот видит стены с помощью лидара и понимает, что стена должна быть закреплена на определенной сетке, он может корректировать свое положение. Ведь мы в этом состязании получаем координаты робота неточные. Они рассчитаны на основе вращения колес. Эти координаты постепенно накапливают ошибку. Поэтому я сделал так, чтобы робот, когда движется по горизонтали или по вертикали, доезжая до стены, корректировал свое положение, зная, где точно эта стена должна располагаться на сетке лабиринта и зная расстояние до нее по лидару.

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

► Прокладка пути

Чтобы дойти до центра лабиринта, как я уже сказал, нельзя просто полагаться на правила левой или правой руки. Нужен более хитрый алгоритм. Я выбрал алгоритм заполнения лабиринта - flood fill.

В чем он заключается? Для каждой точки лабиринта мы рассчитываем вес, который обозначает количество шагов, минимальное количество шагов, за которое можно дойти до цели (в нашем случае до центра). И пока стены этому не препятствуют, лабиринт закрашен равномерным градиентом. B вес клетки зависит от веса соседних клеток. Получается, что вес любой клетки равен минимальному весу любой соседней клетки плюс один. И таким образом закрашен весь лабиринт. У клеток в центре вес, соответственно, ноль, потому что это цель.

По мере того, как робот обнаруживает стены в лабиринте, он пересчитывает веса клеток, прилежащих к новой стене. Веса таким образом могут только увеличиваться. Вес клеточек я визуализировал цветом. Чем клетка темнее, тем больше у нее вес, и значит, тем больше путь нужно пройти роботу, чтобы дойти до центра в этом направлении. На видео хорошо видно, как прокрашиватеся темным длинный коридор, как только робот обнаруживает тупик.

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

В следующем посте расскажу про то, как проходил полуфинал. Там все было уже гораздо сложнее.

- Часть 1

- Часть 2

- Часть 3 (вы здесь)

- Часть 4

#hackathon #mtstruetech #commonlisp #robotics