Micromouse — конкурс для маленьких роботов

Micromouse — это конкурс для маленьких роботов-мышей по поиску пути в центр лабиринта размером 16х16 ячеек. Мероприятие популярно во многих странах, особенно в Великобритании, Японии и Южной Корее. Лабиринт представляет собой сетку из квадратов по 16 штук в длину и ширину, каждый квадрат имеет размеры стен 18 см. и высотой 5 см.


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

Робот может разгоняться до трех метров в секунду. В настоящее время для достижения цели роботу требуется всего несколько секунд, в зависимости от дизайна лабиринта.

Мыши могут использовать различные алгоритмы поиска. Самые популярные это, конечно, A* и вариации алгоритма Беллмана.

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

Сами электронные мыши выглядят по-разному:






На видео робот достигает цели за 3.921 секунды.