SwarmLINEr

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

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

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

Метод роя частиц в общем виде формулируется очень заумно, поэтому давайте попробуем описать его по простому, доступным языком. 

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

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

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

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

В общем виде алгоритм выглядит так:

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

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

Попробуем реализовать алгоритм на практике. Конструкция робота полностью повторяет GeneLINErа,  инструкцию по сборке которого можно скачать по ссылке. Программировать LEGO Mindstorms NXT мы снова будем на полюбившемся нам NXC. Код нашей программы можно скачать здесь.

Первым делом давайте опишем каждую птицу (агента)

struct agent

{

  // скорость агента

  float speed;

  // текущий П-коэффициент ПИД-регулятора у агента

  float Kp;

  // текущий И-коэффициент у агента

  float Ki;

  // текущий Д-коэффициент 

  float Kd;

  // динамика изменения скорости у агента

  float change_speed;

  // динамика изменения П-коэффициента у агента

  float change_Kp;

  // динамика изменения И-коэффициента

  float change_Ki;

  // динамика изменения Д-коэффициента

  float change_Kd;

  // лучшее значение П-коэффициента, найденное агентом

  float best_Kp;

  // лучшее значение И-коэффициента

  float best_Ki;

  // лучшее значение Д-коэффициента

  float best_Kd;

  // скорость, соответствующая лучшим значением коэффициентов

  float best_speed;

  // максимальная длина пути с лучшими из найденных параметров

  long best_path;

  // текущий путь, пройденный за время последнего испытания

  long path;

};

При создании каждого агента случайно сгенерируем его начальные параметры в некотором диапазоне с помощью функции born(). 

В нашем случае мы полагаем что оптимальные параметры лежат в диапазоне

0 < Kp < 2

0 < Ki < 0.1

0 < Kd < 4

0 < speed < 100

а динамику их изменения установим в +/- 2..5%

-0.1 < change_Kp < 0.1

-0.005 < change_Ki < 0.005

-0.2 < change_Kd < 0.2

-2 < change_speed < 2

agent born(){

  agent tmp;

  tmp.speed = Random(70)+30;

  tmp.Kp = Random(2000)/1000.0;

  tmp.Ki= Random(10000)/100000.0;

  tmp.Kd= Random(4000)/1000.0;

  tmp.change_speed=(Random(4000)-2000)/1000.0;

  tmp.change_Kp=(Random(2000)-1000)/10000.0;

  tmp.change_Ki=(Random(1000)-500)/100000.0;

  tmp.change_Kd=(Random(4000)-2000)/10000.0;

  tmp.path = 0;

  tmp.best_path=0;

  return tmp;

}

Создадим 10 птиц (агентов):

agents = 10

agent robot[agents];

for(int i=0;i<agents;i++){

  robot[i]=born();

}

Еще одного агента создадим в качестве хранилища для лучшего найденного решения:

agent best;

Теперь испытаем каждую птицу, "узнаем сколько пищи он нашла" в тех координатах, в которых она сейчас находится. Функция pid() для испытания особей в целом не претерпела изменений по сравнению с GeneLINEr, за исключением последнего параметра - это длительность испытания в миллисекундах.

for (int i=0;i<agents;i++){

      robot[i].path = pid(robot[i].Kp,robot[i].Ki

                      ,robot[i].Kd,robot[i].speed,2000);

  // сохраняем лучшее общее решение, найденное стаей

  if(robot[i].path>best.path){

    best.path=robot[i].path;

    best.speed=robot[i].speed;

    best.Kp=robot[i].Kp;

    best.Ki=robot[i].Ki;

    best.Kd=robot[i].Kd;        

  }

  // сохраняем лучшее решение, найденное каждой птицей

  if(robot[i].path>robot[i].best_path){

    robot[i].best_path=robot[i].path;

    robot[i].best_speed=robot[i].speed;

    robot[i].best_Kp=robot[i].Kp;

    robot[i].best_Ki=robot[i].Ki;

    robot[i].best_Kd=robot[i].Kd;

  }

}

Теперь самое сложное в алгоритме - коррекция скорости, направления полета и положения каждой птицы.

Сначала введем два параметра:

float nostalgia =0.25;

float confidence=0.75;

Nostalgia - это стремление птицы быть поближе к тому месту, где она нашла пищи больше всего. Confidence - стремление птицы быть поближе месту, где пиши больше всего по общему мнению стаи.

Формула для корректировки скорости изменения каждого параметра имеет вид:

СКОРОСТЬ_ИЗМЕНЕНИЯ_ПАРАМЕТРА = СКОРОСТЬ_ИЗМЕНЕНИЯ_ПАРАМЕТРА
              + Nostalgia * СЛУЧАЙНОЕ_ЧИСЛО(0..1)  
              * (ЛУЧШЕЕ_ЗНАЧЕНИЕ_ПАРАМЕТРА_ОСОБИ - ТЕКУЩЕЕ_ЗНАЧЕНИЕ_ПАРАМЕТРА)  
              + Confidence * СЛУЧАЙНОЕ_ЧИСЛО(0..1)  
              * (ЛУЧШЕЕ_ЗНАЧЕНИЕ_ПАРАМЕТРА_СТАИ - ТЕКУЩЕЕ_ЗНАЧЕНИЕ_ПАРАМЕТРА)

Давайте ее проанализируем на примере высоты полета птицы:

• скорость изменения высоты полета основывается на скорости изменения высоты полета в предыдущую единицу времени (то есть у птицы есть инерция)
• чем больше параметр Nostalgia, тем сильнее птица будет стремиться лететь на высоте, на которой она увидела больше всего пищи
• чем выше птица поднимается от той точки, из которой она видела больше всего пищи, тем сильнее замедляется скорость набора высоты (тоже самое со снижением высоты полета)
• чем больше параметр  Confidence, тем сильнее птица будет стремиться лететь на высоте, на которой по общему мнению стаи видно больше всего пищи
• чем выше птица поднимается от той точки, из которой по общему мнению стаи больше всего пищи, тем сильнее замедляется скорость набора высоты (тоже самое со снижением высоты полета)
• СЛУЧАЙНОЕ_ЧИСЛО(0..1) превносит в действия птицы элемент случайности, на каждом шаге птица может более или менее может хотеть действовать самостоятельно или подчиняться мнению стаи, это некие перепады ее настроения.

Формула для корректировки значения параметра выглядит так:

НОВОЕ_ЗНАЧЕНИЕ_ПАРАМЕТРА =
  СТАРОЕ_ИЗМЕНЕНИЯ_ПАРАМЕТРА + СКОРОСТЬ_ИЗМЕНЕНИЯ_ПАРАМЕТРА

В программе это выглядит следующим образом:

for (int i=0;i<agents;i++){

  robot[i].change_Kp = robot[i].change_Kp+nostalgia 

                       * (Random(1000)/1000.0)

                       * (robot[i].best_Kp-robot[i].Kp)

                       + confidence*(Random(1000)/1000.0)

                       * (best.Kp-robot[i].Kp);

  robot[i].Kp=robot[i].Kp+robot[i].change_Kp;

  robot[i].change_Ki = robot[i].change_Ki+nostalgia 

                       * (Random(1000)/1000.0)

                       * (robot[i].best_Ki-robot[i].Ki)

                       + confidence*(Random(1000)/1000.0)

                       * (best.Ki-robot[i].Ki);

  robot[i].Ki=robot[i].Ki+robot[i].change_Ki;

  robot[i].change_Kd = robot[i].change_Kd+nostalgia 

                       * (Random(1000)/1000.0)

                       * (robot[i].best_Kd-robot[i].Kd)

                       + confidence*(Random(1000)/1000.0)

                       * (best.Kd-robot[i].Kd);

  robot[i].Kd=robot[i].Kd+robot[i].change_Kd;

  robot[i].change_speed = robot[i].change_speed+nostalgia 

                          * (Random(1000)/1000.0)

                          * (robot[i].best_speed-robot[i].speed)

                          + confidence*(Random(1000)/1000.0)

                          * (best.speed-robot[i].speed);

  robot[i].speed=robot[i].speed+robot[i].change_speed;

}

Если птица вылетела за пределы территории поиска, она пересоздается:

for (int i=0;i<agents;i++){

  if(robot[i].Kp<=0 || robot[i].Kp>=2 ||

     robot[i].speed<=0 || robot[i].speed>100 ||

     robot[i].Ki<=0 || robot[i].Ki>0.1 ||

     robot[i].Kd<=0 || robot[i].Kd>4){

     robot[i]=born();

}

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

final = pid(best.Kp,best.Ki,best.Kd,best.speed,100000);

По мере улучшения найденного решения будем записывать лучшие найденные параметры в файл, для дальнейшего анализа:

logstr =NumToStr(pok)+ ";"+NumToStr(best.Kp)+";"

        +NumToStr(best.Ki)+";" +NumToStr(best.Kd)+";"

        +NumToStr(best.speed)+";"+NumToStr(best.path);

msg_len = StrLen(logstr);

WriteLnString(fh, logstr, msg_len);