Роботы, лабиринты и архитектура поглощения

Программирование виртуальных роботов на языке Java

В данной статье Пол Рейнер (Paul Reiner) — программист из IBM — показывает, что симуляторы роботов можно рассматривать не только как инструментарий для серьезных научных разработок, но и в качестве способа получить немало удовольствия от программирования на Java™. Читая статью, вы узнаете о создании виртуальных роботов, способных двигаться к источнику света и искать выход из лабиринтов. В процессе разработки мы будем использовать язык Java и симулятор роботов с открытым исходным кодом под названием Simbad, основанный на технологии Java 3D. Симулятор поможет вам получить представление о технологии проектирования роботов, известной, как архитектура поглощения (subsumption architecture).

Пол Рейнерс, программист, IBM

Пол Рейнерс (Paul Reiners) – программист и разработчик Java, сертифицированный Sun. Он автор нескольких open source программ, таких как Automatous Monk, Twisted Life и Leipzig. Пол получил степень магистра прикладной математики со специализацией в теории вычислений в университете Урбаны в Иллинойсе в мае 1991 г., т.е. примерно за 9 месяцев до того, как в том же университете впервые запустили HAL 9000 (это произошло 12 января 1992 г.). Он живет в Миннесоте и посвящает свое свободное время игре на электрогитаре, выступая в составе джаз-группы



07.06.2008

Введение

Робототехника давным давно вышла за пределы научно-фантастических романов и в настоящее время является одной из движущих сил, определяющих прогресс во многих областях, таких как автоматизация производства, медицина, космос и т.д. Важную роль в робототехнике играют программные симуляторы, т.к. они не только упрощают работу инженеров, но и позволяют исследователям испытывать новейшие алгоритмы искусственного интеллекта (AI) и машинного обучения. Одним из таких симуляторов является Simbad – проект с открытым кодом, разработанный на основе технологии Java 3D (см. Ресурсы). В данной статье мы расскажем, как программировать виртуальных роботов, используя инструментарий Simbad, для получения лучшего представления об одной из философий проектирования роботов – архитектуре поглощения (subsumption architecture).

Начало статьи посвящено краткому обзору робототехники и концепции архитектуры поглощения. Затем мы перейдем к инструментарию Simbad и расскажем, как, используя его, можно реализовать данную архитектуру. После этого придет время создания простого робота в соответствии с описанной архитектурой. В конце концов, вы окунетесь в занимательный мир лабиринтов и создадите второго робота, который, подобно Гомеру из Симпсонов (см. Ресурсы), сможет самостоятельно из них выбираться. Разумеется, созданные роботы будут “виртуальными”, т.е. будут жить в виртуальной среде Simbad.


Программирование роботов

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

  • Набора сенсоров
  • Программы, определяющей поведение робота
  • Набора приводов и эффекторов

Традиционная робототехника

Под традиционной робототехникой обычно понимается период развития данной области вплоть до 1986 года. Для того времени было характерно представление о роботе, как о механизме, управляемом центральным контроллером (мозгом), который постоянно обновляет свое представление об окружающем мире и вырабатывает план поведения, исходя из этого представления. Новая информация о мире поступает от сенсоров, например, осязания, света, ультразвука и т.д. Мозг анализирует всю информацию от сенсоров и обновляет представление об окружающей среде, а затем принимает решение о том или ином действии. Все действия выполняются с помощью приводов и эффекторов. Первые обычно представляют собой некие двигатели, подсоединенные к устройствам, непосредственно взаимодействующим с окружающим миром — эффекторам. Примерами последних могут служить колеса или руки. При этом иногда под приводами (actuators) понимаются как сами приводы, так и эффекторы.

Таким образом, традиционный робот получает данные от множества сенсоров, комбинирует эти данные в процессе обновления картины мира, затем вырабатывает план действий на основе данной картины, и наконец, приводит его в исполнение. К сожалению, данный подход сопряжен с определенными трудностями. Во-первых, он требует большого объема вычислений. Во-вторых, поддержка актуальной картины окружающего мира – задача очень сложная, т.к. мир меняется постоянно. При этом известно, что многие организмы, например, насекомые, благополучно существуют и без поддержки полной картины мира, более того, даже не имея памяти как таковой. Так может стоит попробовать перенять их подход к функционированию? Подобные размышления стали отправной точкой нового течения в робототехнике, доминирующего в настоящее время. Оно получило название “поведенческая робототехника” (behavior-based robotics - BBR).

Архитектура поглощения

Одним из способов организации BBR-роботов является архитектура поглощения, предложенная в 1986 г. Родни Бруксом (Rodney A. Brooks) — в настоящее время главой лаборатории искусственного интеллекта в Массачусетском Технологическом Институте (MIT) — в его фундаментальной статье под названием “Слоны не играют в шахматы” (см. Ресурсы). Согласно Бруксу, поведенческие роботы можно рассматривать как набор простых и независимых поведенческих узлов (behaviors), каждый из которых определяется двумя вещами – тем, что вызывает данное поведение (как правило, информация, поступающая от сенсоров), и тем действием, что является его результатом (как правило, выполненным с помощью эффектора). Поведения могут наслаиваться друг на друга, а также конфликтовать между собой. В этом случае, в действие вступает специальный механизм арбитража, который решает, какое поведение в данный момент является приоритетным. Ключевым моментом является то, что поведение робота, как единого целого, не закладывается заранее, а вырисовывается из взаимодействия его поведенческих узлов. Более того, по мнению сторонников BBR, глобальное поведение является чем-то большим, чем просто суперпозицией его частей. Оно поглощает каждое из локальных, низкоуровневых поведений. В целом, идея заключается в том, что вместо проектирования робота и точного описания его поведения во всех ситуациях, можно просто добавлять поведенческие узлы и смотреть, что получится в результате.


Simbad: среда для моделирования роботов

LEGO Mindstorms

В данной статье рассматривается создание программных агентов (ботов), но если вас интересуют реальные физические роботы, то обратите внимание на LEGO Mindstorms – замечательный инструментарий для робототехника.

Слоган в штаб-квартире LEGO Mindstorms гласит: “Мы сделаем для робототехники то, что iPod сделал для музыки” ("We will do for robotics what iPod did for music"). Первая версия Mindstorms была представлена в 1998 г. и сразу же превзошла ожидания LEGO по объему продаж. Цена комплекта ($250) может показаться слегка завышенной, но не забывайте, что столько же стоит iPod Classic, а он есть практически у каждого.

При этом iPod не предоставляет собой такого интереса для взлома как Mindstorms. Стоило выйти первому релизу Mindstorms, как различного рода хакеры начали взламывать и анализировать блоки RCX, являющиеся “мозгами” роботов. LEGO пребывала в некотором недоумении и сначала не могла решить, оставить ли все как есть или же выпустить официальное требование прекратить подобные действия. К чести руководства компании, они решили предоставить хакерам полную свободу действий в отношении Mindstorms.

Это привело к расцвету сообщества Mindstorms (см. Ресурсы). Одним из следствий стало стороннее портирование платформы Mindstorms под другие языки, такие как C и Java, в то время, как сам инструментарий изначально поставлялся только вместе с графическим языком программирования NXT-G. В итоге, более половины пользователей инструментария – это взрослые специалисты.

Simbad предназначен для программного моделирования роботов. Согласно Web-странице проекта, Simbad “предоставляет программные средства для разработки роботов, описания их воздействия на окружающий мир, а так же использования сенсоров. Simbad был в первую очередь разработан для исследователей, которым необходим простой инструментарий для изучения ситуационного искусственного интеллекта, машинного обучения и алгоритмов AI вообще, особенно применительно к автономным роботам и агентам”.

Simbad был разработан на Java Луи Уге (Louis Hugue) и Николя Бредешем (Nicolas Bredeche). Проект размещен на сервере SourceForge.net и может свободно использоваться или модифицироваться в соответствии с лицензией GNU GPL (General Public License).

Технические подробности

Мир в среде Simbad может содержать как агентов (роботов), так и различные неодушевленные предметы, такие как, ящики, стены, источники света и т.д. Время в этом мире дискретно, т.е. разбито на интервалы. Simbad включает в себя планировщик, распределяющий время между агентами. Аналогично реальным роботам, агенты Simbad имеют как сенсоры (датчики расстояния, осязания, света и т.д.), так и приводы (как правило, колеса). В любой отведенный ему момент времени, робот может выполнять какое-то действие.

Классы, реализующие агентов, должны переопределять метод performBehavior(), который описывает их поведение. Внутри этого метода робот может анализировать поступающую от сенсоров информацию и изменять вращательную и поступательную составляющие скорости движения. На исполнение метода performBehavior() отводится короткий промежуток времени, поэтому нельзя отдавать такие команды, как, например, “продвинуться вперед на один метр”. Для того чтобы обойти это ограничение как правило приходится постоянно контролировать состояние, в котором находится робот. Кроме этого можно использовать таймер для отслеживания количества временных интервалов, в течение которых робот находился в текущем состоянии.

Simbad API

В примерах к данной статье в основном затрагиваются вопросы, связанные со следующими двумя пакетами, входящими в состав Simbad API:

  • simbad.sim: Классы данного пакета описывают как самих роботов, так и окружающий их мир. Основными классами являются:
    • Agent: Сами роботы.
    • Arch: Арки, которые роботы могут объезжать либо проезжать под ними.
    • Box: Описывают препятствия на пути робота.
    • CameraSensor: Позволяет получать доступ к картине окружающего мира с точки зрения робота.
    • EnvironmentDescription: Описывает среду, в которую можно добавлять как роботов, так и неодушевленные объекты, например, стены и другие препятствия.
    • LampActuator: Фары, которые можно добавлять к своему роботу.
    • LightSensor: Сенсоры света.
    • RangeSensorBelt: Набор датчиков расстояния, которые могут быть расположены по периметру робота.
    • RobotFactory: Используется для добавления различных сенсоров к роботу.
    • Wall: Еще один тип препятствия для движения робота.
  • simbad.gui: Классы из данного пакета отображают самого робота и позволяют его контролировать. Основным классом являются следующий:
    • Simbad: Окно, отображающее картину мира робота, информацию, поступающую с его сенсоров, а так же управляющие элементы.

Реализация архитектуры поглощения с помощью Simbad

Румба

В то время как я пишу эти строки, Румба (Roomba) пылесосит ковер у меня под ногами (при этом периодически наталкиваясь на котенка). Румба – это робот, разработанный компанией iRobot, основанной тремя выпускниками MIT: Родни Бруксом, Колином Энглом (Colin Angle) и Хелен Грейнер (Helen Greiner). Он был создан в согласии с принципами архитектуры поглощения и предоставляет открытый интерфейс, позволяющий менять его поведение самым произвольным образом. Книга Тода Курта (Tod E. Kurt) “Взламывая Румбу” рассказывает о множестве таких возможностей (см. Ресурсы).

Реализовывать архитектуру поглощения на основе Simbad мы начнем с объявления класса-потомка Agent под названием BehaviorBasedAgent. Каждый экземпляр данного класса будет содержать массив поведений (объектов типа Behavior), а так же булеву матрицу, хранящую информацию об их попарном поглощении.

private Behavior[] behaviors;
private boolean suppresses[][];

Класс BehaviorBasedAgent выступает в роли планировщика поведений. В листинге 1 приведен фрагмент кода, итерирующего по массиву поведений и регулирующего их запуск. При этом переменная currentBehaviorIndex используется для хранения ссылки на поведение, которое должно быть активировано на следующем шаге алгоритма.

Листинг 1. Цикл для поочередной активации поведений и разрешения конфликтов
protected void performBehavior() {
   boolean isActive[] = new boolean[behaviors.length];
   for (int i = 0; i < isActive.length; i++) {
      isActive[i] = behaviors[i].isActive();
   }
   boolean ranABehavior = false;
   while (!ranABehavior) {
      boolean runCurrentBehavior = isActive[currentBehaviorIndex];
      if (runCurrentBehavior) {
         for (int i = 0; i < suppresses.length; i++) {
            if (isActive[i] && suppresses[i][currentBehaviorIndex]) {
               runCurrentBehavior = false;

               break;
            }
         }
      }

      if (runCurrentBehavior) {
         if (currentBehaviorIndex < behaviors.length) {
            Velocities newVelocities = behaviors[currentBehaviorIndex].act();
            this.setTranslationalVelocity(newVelocities
                  .getTranslationalVelocity());
            this
                  .setRotationalVelocity(newVelocities
                        .getRotationalVelocity());
         }
         ranABehavior = true;
      }

      if (behaviors.length > 0) {
         currentBehaviorIndex = (currentBehaviorIndex + 1)
               % behaviors.length;
      }
   }
}

Отметьте, что метод performBehavior() перегружает аналогичный метод в классе simbad.sim.Agent.

В классе поведения Behavior объявлено два абстрактных (abstract) метода:

  • isActive(): Метод возвращает булево значение, показывающее, должно ли данное поведение быть активировано в данный момент времени, учитывая информацию, поступающую от сенсоров. При этом все экземпляры класса Behavior имеют доступ к общему набору сенсоров.
  • act(): Метод возвращает новые значения поступательной и вращательной скорости (именно в таком порядке), являющиеся результатом активации поведения.

Пример блуждающего робота, притягивающегося к источникам света

Теперь пришло время создать программного робота (или бота), который будет включать 4 нижеперечисленных поведения, хранящихся в порядке убывания приоритета. Код бота показан в листингах со второго по пятый (код примеров к данной статье доступен для скачивания).

  • Avoidance: Изменяет направление движения после столкновения или в попытке предотвратить столкновение.
  • LightSeeking: Направляет движение в сторону источника света.
  • Wandering: Периодически меняет направление движения произвольным образом.
  • StraightLine: Направляет движение по прямой.
Листинг 2. Класс Avoidance (на основе демонстрационного примера SingleAvoiderDemo.java из поставки Simbad)
public boolean isActive() {
   return getSensors().getBumpers().oneHasHit()
         || getSensors().getSonars().oneHasHit();
}

public Velocities act() {
   double translationalVelocity = 0.8;
   double rotationalVelocity = 0;
   RangeSensorBelt sonars = getSensors().getSonars();
   double rotationalVelocityFactor = Math.PI / 32;
   if (getSensors().getBumpers().oneHasHit()) {
      // Произошло столкновение
      translationalVelocity = -0.1;
      rotationalVelocity = Math.PI / 8
            - (rotationalVelocityFactor * Math.random());
   } else if (sonars.oneHasHit()) {
      // Считывание показаний эхолокаторов
      double left = sonars.getFrontLeftQuadrantMeasurement();
      double right = sonars.getFrontRightQuadrantMeasurement();
      double front = sonars.getFrontQuadrantMeasurement();
      // Препятствие близко
      if ((front < 0.7) || (left < 0.7) || (right < 0.7)) {
         double maxRotationalVelocity = Math.PI / 4;
         if (left < right)
            rotationalVelocity = -maxRotationalVelocity
                  - (rotationalVelocityFactor * Math.random());
         else
            rotationalVelocity = maxRotationalVelocity
                  - (rotationalVelocityFactor * Math.random());
         translationalVelocity = 0;
      } else {
         rotationalVelocity = 0;
         translationalVelocity = 0.6;
      }
   }

   return new Velocities(translationalVelocity, rotationalVelocity);
}
Листинг 3. Класс LightSeeking (на основе демонстрационного примера LightSearchDemo.java из поставки Simbad)
public boolean isActive() {
   float llum = getSensors().getLightSensorLeft().getAverageLuminance();
   float rlum = getSensors().getLightSensorRight().getAverageLuminance();
   double luminance = (llum + rlum) / 2.0;

   // Активизироваться если источник света неподалеку
   return luminance > LUMINANCE_SEEKING_MIN;
}

public Velocities act() {
   // Повернуть в сторону источника света
   float llum = getSensors().getLightSensorLeft().getAverageLuminance();
   float rlum = getSensors().getLightSensorRight().getAverageLuminance();
   double translationalVelocity = 0.5 / (llum + rlum);
   double rotationalVelocity = (llum - rlum) * Math.PI / 4;

   return new Velocities(translationalVelocity, rotationalVelocity);
}
Листинг 4. Класс Wandering
public boolean isActive() {
   return random.nextDouble() < WANDERING_PROBABILITY;
}

public Velocities act() {
   return new Velocities(0.8, random.nextDouble() * 2 * Math.PI);
}
Листинг 5. Класс StraightLine class
public boolean isActive() {
   return true;
}

public Velocities act() {
   return new Velocities(0.8, 0.0);
}

В листинге 6 показано поглощение одних поведений другими.

Листинг 6. Объявление булевой матрицы, описывающей попарное поглощение поведений
private void initBehaviorBasedAgent(BehaviorBasedAgent behaviorBasedAgent) {
   Sensors sensors = behaviorBasedAgent.getSensors();
   Behavior[] behaviors = { new Avoidance(sensors),
         new LightSeeking(sensors), new Wandering(sensors),
         new StraightLine(sensors), };
   boolean subsumes[][] = { { false, true, true, true },
         { false, false, true, true }, { false, false, false, true },
         { false, false, false, false } };
   behaviorBasedAgent.initBehaviors(behaviors, subsumes);
}

В данном примере набор поведений полностью упорядочен в соответствии с приоритетом. В общем случае, это необязательно.

В качестве упражнения вы можете попробовать реализовать следующие вещи:

  • Социальное поведение: движение навстречу друзьям и в сторону от врагов.
  • Избегание источников света.
  • Добавить фары к некоторым роботам, так, чтобы они начали притягиваться друг к другу.

Лабиринты

"Ну, наконец-то! Я так и знала, что из этого лабиринта можно выбраться, действуя по алгоритму Тремо!" — Лиза Симпсон

Из всей массы алгоритмов выхода из лабиринтов, два выделяются тем, что используют объем памяти, не зависящий от размера самого лабиринта. Они известны под названиями “следование вдоль стены” (wall-following) и алгоритм Пледжа. Последний был назван в честь Джона Пледжа (Jon Pledge) из Эксетера, который изобрел алгоритм в возрасте 12 лет. Кроме этого есть еще великолепный алгоритм Тремо (Tremaux algorithm) – любимый алгоритм Лизы Симпсон – но в целях упрощения мы рассмотрим только первые два.

Алгоритмы генерации лабиринтов

Интерес представляют не только алгоритмы выхода из лабиринтов, но и их генерации. Лабиринты, рассматриваемые в данной статье, называются совершенными (perfect), благодаря тому, что существует один и только один вариант прохода между любыми двумя точками лабиринта. Благодаря этому условию исключаются петли, острова, а так же изолированные участки. Большинство алгоритмов, генерирующих совершенные лабиринты, работают следующим образом: они начинают с простого лабиринта, представляющего собой только внешнюю стену и постепенно добавляют внутренние участки. При этом на каждом шаге необходимо исключать возможность появления петель, изолированных секций и т.д.

Следование вдоль стены

Этот алгоритм настолько прост, что многие обучаются ему еще в детстве. Все что требуется для выхода — это вести левой рукой по левой стене (или правой рукой по правой стене) пока не встретите выход. Несложно видеть, что данный алгоритм работает безупречно для лабиринтов, в которых вход и выход расположены на периметре. К сожалению, алгоритм нельзя применять в случае, если выход расположен на острове — части лабиринта, не соединенной с остальными стенами. В этой ситуации алгоритм не найдет выход, потому что нельзя перепрыгнуть пустое пространство до острова, не отрывая руку от стены.

Алгоритм Пледжа

Алгоритм Пледжа более сложен, но зато способен находить выход из большего числа лабиринтов за счет возможности переходов от одного острова к другому. Идея алгоритма заключается в том, что надо выбрать некое абсолютное направление (север, юг, запад или восток) и всегда стараться ему следовать. Назовем его предпочтительным направлением. В случае если вы упираетесь в стену, вы поворачиваете направо и движетесь в соответствии с алгоритмом “следование вдоль стены” до тех пор, пока не выполнится два условия. Первое – это поворот в предпочтительном направлении, а второе – сумма всех ранее сделанных поворотов равна нуля (при этом каждый поворот против часовой стрелки принимается за единицу, а по часовой стрелке, соответственно, за минус единицу). После этого вы продолжаете двигаться в предпочтительном направлении пока это возможно и так далее. Условие на нулевую сумму поворотов необходимо для избегания разного рода ловушек, например, участков лабиринтов, имеющих форму G (нарисуйте ее на бумаге и сразу поймете, о чем я).


Алгернон: робот, выбирающийся из лабиринтов

Пришло время удивить ваших друзей, создав робота по имени Алгернон (Algernon), задачей которого будет выход из лабиринтов.

Проектирование робота

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

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

Реализация алгоритма следования вдоль стены

Весь код Алгернона будет размещен в пакете algernon.subsumption (весь код доступен для скачивания). Алгернон — это достаточно простой робот и его вполне можно запрограммировать в процедурном стиле. В то же время, даже для такого простого робота, подход, основанный на поглощении поведений, делает код намного чище, легче для понимания, а также способствует лучшей организации модулей.

Мы сделаем еще одно допущение в целях упрощения примера: будем считать, что все стены пересекаются под прямыми углами. Другими словами, все повороты налево и направо осуществляются исключительно на 90 градусов.

Леворукий алгоритм следования вдоль стены можно декомпозировать на четыре различных поведения:

  • Идти прямо.
  • Упершись в стену, повернуть направо.
  • Встретив ответвление влево, повернуть.
  • Остановиться при нахождении выхода.

Поведениям необходимо присвоить приоритеты. В данном примере, мы их выберем в том же порядке, в каком они перечислены выше. В итоге нам понадобятся четыре класса-наследника Behavior:

  • GoStraight
  • TurnRight
  • TurnLeft
  • ReachGoal

В листинге 7 показан код класса GoStraight, в котором TRANSLATIONAL_VELOCITY – это константа, равная 0.4:

Листинг 7. Реализация поведения для движения по прямой
public boolean isActive() {
   return true;
}
  
public Velocities act() {
   double rotationalVelocity = 0.0;

   return new Velocities(TRANSLATIONAL_VELOCITY, rotationalVelocity);
}

Код класса TurnRight показан в листинге 8. Метод getRotationCount() возвращает количество временных интервалов, необходимых для поворота на 90 градусов при данной скорости вращения.

Листинг 8. Реализация поведения для поворота направоBehavior code for turning right
public boolean isActive() {
   if (turningRightCount > 0) {
      return true;
   }

   RangeSensorBelt bumpers = getSensors().getBumpers();
   // Проверка переднего бампера.
   if (bumpers.hasHit(0)) {
      backingUpCount = 10;
      turningRightCount = getRotationCount();

      return true;
   } else {
      return false;
   }
}
        
public Velocities act() {
   if (backingUpCount > 0) {
      // Робот уперся в стену. Надо чуть отойти назад перед поворотом
      backingUpCount--;

      return new Velocities(-TRANSLATIONAL_VELOCITY, 0.0);
   } else {
      turningRightCount--;

      return new Velocities(0.0, -Math.PI / 2);
   }
}

Для поворота налево, Алгернон должен сначала чуть продвинуться вперед так, что стена слева от него закончится. Затем он поворачивается налево и проходит еще немного вперед так что, по его левую сторону опять находится стена. Код показан в листинге 9.

Листинг 9. Реализация поведения для поворота налево
public boolean isActive() {
   if (postGoingForwardCount > 0) {
      return true;
   }

   RangeSensorBelt sonars = getSensors().getSonars();
   // Проверка эхолокатора слева
   if (sonars.getMeasurement(1) > 1.0) {
      // Слева коридор
      preGoingForwardCount = 20;
      postGoingForwardCount = 40;
      turnLeftCount = getRotationCount();

      return true;
   } else {
      return false;
   }
}
        
public Velocities act() {
   if (preGoingForwardCount > 0) {
      preGoingForwardCount--;

      return new Velocities(TRANSLATIONAL_VELOCITY, 0.0);
   } else if (turnLeftCount > 0) {
      turnLeftCount--;

      return new Velocities(0.0, Math.PI / 2);
   } else {
      postGoingForwardCount--;

      return new Velocities(TRANSLATIONAL_VELOCITY, 0.0);
   }
}

Код класса ReachGoal показан в листинге 10.

Листинг 10. Поведение при обнаружении выхода из лабиринта
public boolean isActive() {
   RangeSensorBelt sonars = getSensors().getSonars();

   // Впереди открытое пространство? Другими словами, нашли ли мы выход из лабиринта?
   double clearDistance = 1.2;
   return sonars.getMeasurement(0) > clearDistance
         && sonars.getMeasurement(1) > clearDistance
         && sonars.getMeasurement(3) > clearDistance
         && sonars.getMeasurement(2) > clearDistance;
}

public Velocities act() {
   // Остановка
   return new Velocities(0.0, 0.0);
}

Главный метод, определяющий поведение Алгернона приведен в листинге 11.

Листинг 11. Код управления поведениями Алгернона
private void initBehaviorBasedAgent(
      algernon.subsumption.BehaviorBasedAgent behaviorBasedAgent) {
   algernon.subsumption.Sensors sensors = behaviorBasedAgent.getSensors();
   algernon.subsumption.Behavior[] behaviors = { new ReachGoal(sensors),
         new TurnLeft(sensors), new TurnRight(sensors),
         new GoStraightAlways(sensors) };
   boolean subsumes[][] = { { false, true, true, true },
         { false, false, true, true }, { false, false, false, true },
         { false, false, false, false } };
   behaviorBasedAgent.initBehaviors(behaviors, subsumes);
}

На рисунке 1 показано, как Алгернон движется по лабиринту.

Рисунок 1. Алгернон, двигающийся по лабиринту
Algernon running a maze

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


Заключение

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

Обратите внимание на инструментарий LEGO Mindstorms, если вы заинтересовались проектированием и программированием роботов. В качестве альтернативы, можно поработать с роботами BEAM (Biological Electronic Aesthetics Mechanics). BEAM далее развивает идею поведенческой робототехники, вообще убирая программирование как таковое. Глобальное поведение робота определяется жестко заданными соединениями поведенческих узлов, работающих на рефлексах. Заплатив не более $30 вы сможете построить своего первого BEAM-робота. Также можно спроектировать робота по чертежам, которые вы найдете в книге Гарета Бранвина (Gareth Branwyn) “Создание роботов для абсолютных новичков” (см. Ресурсы). Ну и, наконец, всегда можно купить Румбу и взломать его.

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

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

Ресурсы

Научиться

  • Оригинал статьи: "Robots, mazes, and subsumption architecture". (EN)
  • Посетите страницу проекта Simbad и скачайте среду для моделирования роботов. (EN)
  • Отличное введение в робототехнику как хобби приведено в книге “Создание роботов для абсолютных новичков” (Гарет Бранвин (Gareth Branwyn), Que, 2003 г.). (EN)
  • В книге “Мобильные роботы” (Джозеф Джонс (Joseph L. Jones), Анита Флинн (Anita M. Flynn), A K Peters Ltd., 1998 г.) рассказывается о проектировании и реализации простых, недорогих робот, а также подробно объясняется архитектура поглощения. Книга особенно полезна за счет ясного изложения идей и концепций робототехники. Флинн и Джонс в свое время были студентами Родни Брукса в лаборатории искусственного интеллекта в MIT. (EN)
  • В статье “Открытые инструментарии для создания роботов” (М. Тим Джонс (M. Tim Jones), developerWorks, сентябрь 2006 г.) приводится обзор программных средств для тестирования алгоритмов функционирования роботов, в том числе и Simbad. (EN)
  • Общее введение в роботехнику и открытое программное обеспечения для управления роботами приведено в статье “Введение в робототехнику” (Дэррик Эддисон (Darrick Addison), developerWorks, сентябрь 2001 г.). (EN)
  • В книге “Плоть и машины” (Родни Брукс, Pantheon Books, 2002) Родни Брукс рассказывает в занимательной и общедоступной манере о предложенной им поведенческой философии в робототехнике. (EN)
  • Симпсоны: познакомьтесь с семьей Симпсонов – легендой американского телевидения. В эпизоде “Стой! А то моя собака будет стрелять!” Лиза Симпсон помогает семейке выбраться из лабиринта, используя алгоритм Тремо. (EN)
  • В книге “Создание роботов с помощью LEGO Mindstorms NXT” (Дэйв Астолфо (Dave Astolfo), Марио Феррари (Mario Ferrari) и Джулио Феррари (Giulio Ferrari) , Syngress Publishing, 2007 г.) приводится глава, посвященная разработке роботов для навигации по лабиринтам. (EN)
  • Статья “Хакеры в Стране Игрушек” (Брендан Кернер (Brendan I. Koerner), Wired, февраль 2006 г.) рассказывает о процессе разработки LEGO Mindstorms NXT и о помощи, оказанной хакерами. (EN)
  • Множество способов проникновения и изменения поведения Румбы приведено в книге “Взламывая Румбу” (Тод Курт (Tod E. Kurt), Wiley, 2007 г.). Например, рассказывается, как заставить Румбу петь или рисовать, как установить на нем Linux® или даже использовать его в качестве мыши (а почему нет?). (EN)
  • Захватывающую информацию о лабиринтах можно найти в книге “Черепашья геометрия” (Гарольд Абельсон (Harold Abelson) и Андреа ди Сесса (Andrea diSessa), MIT Press, 1986 г.). (EN)
  • Документальный фильм “Быстрый, дешевый и неконтролируемый” Эррола Морриса (Errol Morris) включает в себя интервью с Родни Бруксом. Кроме этого, в фильме есть интервью с укротителем львов, садовником и лучшим в мире специалистом по лысым кротам. (EN)
  • Великолепный обзор лабиринтов и связанных с ними алгоритмов можно найти на Web-странице “Размышления о лабиринтах: алгоритмы”, созданной экспертом по лабиринтам Уолтером Палленом (Walter D. Pullen). (EN)
  • Обратитесь к вводной статье в Wikipedia, посвященной лабиринтам. (EN)
  • Обратитесь к магазину технической книги, в котором представлены книги на данную и другие темы. (EN)
  • Обратитесь к разделу Технологии Java на developerWorks, содержащему множество статей по всем вопросам программирования на Java.

Получить продукты и технологии

  • Зайдите на страницу Алгернона, представляющего собой активный проект с открытым кодом. Вы можете примерах к данной статье. (EN)скачать исходный код, использованный в примерах к данной статье. (EN)
  • Скачайте инструментарий Simbad. (EN)

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=312697
ArticleTitle=Роботы, лабиринты и архитектура поглощения
publish-date=06072008