понедельник, 28 февраля 2011 г.

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

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

Например,
1. Робот, двигающийся вдоль правых стенок – выполняет меньше ненужных обходов, т.е. придет к финишу быстрее. Общая длина ненужных обходов для него 1 ячейка, в то время как роботу, двигающемуся вдоль левых стенок – нужно сделать ненужных проходов длиной в 3 ячейки (одна в четвертом коридоре и две в пятом).


2. На этом поле, робот, движущийся по "Правилу левой руки", придет к финишу раньше. 2 ячейки против 4-х.


3. В данной конфигурации количество "лишних" заходов у обоих роботов – одинаково (по 2 ячейки).


Эти три примера показывают, что для разных конфигураций лабиринтов эффективными будут разные алгоритмы. Но это нерепрезентативная выборка.

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

Всего различных возможных вариантов установки перегородок  243  
"Разумных" вариантов, когда не никакие три сподряд идущие перегородки не будут установлены в одинковые позиции
  180  

Если теперь рассмотреть варианты прохода для каждой конфигурации лабиринта, то получится такая вот статистика:

Где
  • в первой строчке – идеальные конфигурации – робот не сделает ни одного ненужного заворота.
  • остальных строчки для проходов с одним или несколькими "ненужными" заворотами в тупики. Причем, если написано два «ненужных» прохода, то это может быть заворот в один длинный тупик или два коротких – в любом случае, на их проходы тратиться почти одинаковое время.
  • в последней строчке – сколько "ячеек" придется посетить при самой неудачной конфигурации лабиринта.

Из таблицы видно, что в 45 конфигурациях лабиринта из 180 робот, обходящий алгоритм по "Правилу левой руки", будет делать только верные перемещения. В то время как роботу, выполняющий программу по "Правилу правой руки" доступно только 13 таких конфигураций. Даже на то, что роботу выпадет конфигурация в которой ему придется сделать все го лишь два "ненужных" прохода., вероятность больше в случае "Правила левой руки" - 41 к 180, тогда как у "Правила правой руки" - всего 36 к 180.

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

Причем, если вспомнить о необходимости собирать шарики по пути движения робота (а они лежать в строго определенных позициях в 3-ем, 4-ом и 5-ом коридорах), статистика несильноизменится.

Допустим, вы сделали достаточно умного робота, способного определять что он находися в нужном коридоре и ему нужно сделать лишний заворот для захвата шарика, даже если "верный" ход для движения к финишу находится не в этом направлении.


Назовем этот маневр также "ненужным" ходом, тогда табличка станет выглядеть следующим образом:


Т.е. варианты попасть на "хорошее" поле у робота, работающего по "Правилу левой руки" все еще существенно выше.

2 комментария:

  1. Для Автора - спасибо за изложенные алгоритмы правой и левой руки, но в реальном лабиринте на стенках присутствуют небольшие выступы, которые усложняют применение этих алгоритмов, поэтому в соревнованиях, если топология лабиринта известна и расстановка перегородок и шариков перед каждым заездом не изменяется, самым оптимальным (по быстродействию и сложности программы) вариантом является программирование робота на проезд по наперёд заданному маршруту. Т.е. к сожалению для развития мышления жертвуем универсальностью в угоду скорости и простоте. Андрей

    ОтветитьУдалить
  2. Спасибо за совет.

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

    ОтветитьУдалить

Related Posts Plugin for WordPress, Blogger...