воскресенье, 27 февраля 2011 г.

Робот для состязаний: выход из лабиринта. Часть II

В предыдущей заметке было описано "Правило правой руки" для поиска выхода из лабиринтов. Давайте посмотрим, как работает это правило для достижения финиша в задании для младшей группы Международной робототехнической олимпиады.
Согласно заданию, лабиринт состоит из шести секций, соединенных между собой проходами. Конфигурация проходов заранее неизвестна. Таким образом, одно из возможных конфигураций лабиринта будет выглядеть следующим образом:


Где зеленая секция – место старта робота, а красная секция – место финиша.

Напомним, что идея "Правила правой руки" состоит в том, что роботу все время необходимо двигаться "держась" правой стенки. Обрыв стены означает для робота, поиск ее с правой стороны. Если перед роботом возникает препятствие , то робот выполняет левый поворот, так что препятствие становится по правую сторону и используется роботом к новая "опора", вдоль которой нужно перемещаться.

Как результат, траекторию движения робота в приведенной выше конфигурации лабиритна можно будет отобразить как:

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

А что если для поиска опоры использовать не правую, а левую руку? Тогда методика обхода лабиринта будет уже называться "Правилом левой руки". В ней все действия будут аналогичны, только направление движения будет меняться: роботу все время необходимо двигаться "держась" левой стенки. Обрыв стены означает для робота, поиск ее с левой стороны. Если перед роботом возникает препятствие , то робот выполняет правый поворот, так что препятствие становится по левую сторону и используется роботом к новая "опора", вдоль которой нужно перемещаться.

Траектория движения в этом же лабиринте изменится:

Очевидно, что "Правило левой руки" дает более оптимальную траекторию – т.е. робот сможет проехать лабиринт за меньшее время. И в первую очередь, в данном конкретном задании, это обуславливается положением старта и финиша в лабиринте.

1 комментарий:

Related Posts Plugin for WordPress, Blogger...