Хабрахабр

[Перевод] Модульные боты-муравьи с памятью

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

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

На это меня сподвиг конкурс по реализации процедурного сада в сабреддите /r/proceduralgeneration (отсюда и соответствующая тема). Я уже реализовал базовую систему конвейера задач на Javascript (потому что это упростило мою жизнь), но мне хотелось чего-то более надёжного и масштабируемого, поэтому этот проект я написал на C++.

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

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

Это должно было стать симуляцией низкого разрешения. Для модели населения (и его «памяти») я просто создал класс с несколькими характеристиками и координатами. Память — это очередь, боты осматриваются по сторонам, сохраняют информацию о своём окружении, записывают в очередь и управляют этой очередью как интерпретацией своей памяти.

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

Пример карты. Вода приняла форму реки совершенно ненамеренно. Все другие элементы расположены случайно, в том числе и муравейник, который в этом seed смещён слишком далеко к краю (но река выглядит красиво).

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

Также я хочу показать некоторые забавные «утечки памяти муравьёв», с которыми можно столкнуться, когда муравьи начинают безумно бегать кругами в поискать травы или стоять на месте и заставлять программу тормозить. Я подробнее хочу описать структуру систем задач и памяти, а также показать, как создавалась сложность из (в основном) примитивных базовых функций.

Общая структура

Я написал эту симуляцию на C++, а для рендеринга использовал SDL2 (раньше я уже написал небольшой класс представления для SLD2). Также я использовал реализацию A* (слегка изменённую), которую нашёл на github, потому что моя реализация была безнадёжно медленной, и я не мог понять, почему.

Класс мира также обрабатывает различные косметические функции, например, рост травы и растительности. Карта — это просто сетка 100×100 с двумя слоями — слоем почвы (используется для поиска путей) и слоем заливки (для выполнения задач взаимодействия и поиска путей). Я говорю об этом сейчас, потому что это единственные части, которые не будут описаны в статье.

Население

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

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

Очередь памяти

Очередь памяти — это простая очередь, содержащая набор объектов памяти, ограниченных по размеру свойством бота. При каждом добавлении новых воспоминаний они выталкивались вперёд, а всё, что выходило за границы сзади, отрезалось. Благодаря этому одни воспоминания могли быть более «свежими», чем другие.

Затем функция вспоминания возвращала вектор воспоминаний, соответствующих любому или всем критериям, указанным в запросе. Если бот хотел вспомнить информацию из памяти, то он создавал объект памяти (запрос) и сравнивал его с находившимся в памяти.

class Memory; //Memory Attributes std::string object; std::string task; Point location; bool reachable;

Воспоминания состоят из простого объекта, содержащего несколько свойств. Эти свойства памяти считаются «ассоциированными» друг с другом. Также каждому воспоминанию задаётся величина «recallScore», которая итерируется каждый раз, когда воспоминания вспоминаются функцией recall. Каждый раз, когда бот вспоминает воспоминания, он выполняет сортировку в один проход по очереди, начиная сзади, меняя порядок воспоминаний, если recallScore более старого воспоминания выше, чем у нового. Благодаря этому некоторые воспоминания могут быть более «важными» (при больших размерах памяти) и дольше сохраняться внутри очереди. Со временем они будут вытеснены новыми.

Очереди памяти

Также я добавил в этот класс несколько перегруженных операторов, чтобы можно было выполнять прямые сравнения между очередью памяти и запросом, сравнивая «любые» или «все» свойства, чтобы при перезаписи памяти переписывались только указанные свойства. Благодаря этому у нас может быть память объекта, связанная с каким-то местом, но если мы заглядываем в это место снова и объекта там нет, мы можем обновить память, перезаписав её памятью, содержащей новый тайл заливки, с помощью запроса, соответствующего этому месту.

void Bot::updateMemory(Memory &query, bool all, Memory &memory){ //Loop through all existing Memories //"memories" queue is a member of Bot for(unsigned int i = 0; i < memories.size(); i++){ //If all matches are required and we have all matches if(all && (memories[i] == query)){ //We have a memory that needs to be updated memories[i] = memory; continue; } //If not all matches are required and any query elements are contained else if(!all && (memories[i] || query)){ //When overwriting, only overwrite specified quantities memories[i] = memory; continue; } }
}

В процессе создания кода этой системы я многому научился.

Система задач

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

В этом разделе я объясню два взгляда на структуру системы задач, предназначенной для противодействия этому эффекту.

Структура «снизу вверх»

Я решил двигаться снизу вверх и создать набор «примитивных действий», которые должны выполнять боты. Каждое из этих действий длится всего один такт. Имея хорошую библиотеку примитивных функций, мы сможем комбинировать их в сложные действия, состоящие из нескольких примитивных.

Примеры таких примитивных действий:

//Primitives
bool wait(Garden &garden, Population &population, int (&arguments)[10]);
bool look(Garden &garden, Population &population, int (&arguments)[10]);
bool step(Garden &garden, Population &population, int (&arguments)[10]);
bool swap(Garden &garden, Population &population, int (&arguments)[10]);
bool store(Garden &garden, Population &population, int (&arguments)[10]);
bool consume(Garden &garden, Population &population, int (&arguments)[10]);
bool move(Garden &garden, Population &population, int (&arguments)[10]); //Continue with secondaries here...

Заметьте, что эти действия содержат ссылки и на мир, и на население, позволяющие изменять их.

  • Wait заставляет существо ничего не делать в этом цикле.
  • Look парсит окружение и записывает в очередь новые воспоминания.
  • Swap берёт предмет в руке существа и заменяет его на лежащий на земле.
  • Consume уничтожает предмет в руке существа.
  • Step берёт текущий вычисленный путь в точку назначения и выполняет один шаг (с кучей проверок на ошибки).
  • … и так далее.

Все функции задач являются членами моего класса задач; после тщательного тестирования они доказали свою надёжность и способность комбинирования в более сложные задачи.

//Secondaries
bool walk(Garden &garden, Population &population, int (&arguments)[10]);
bool idle(Garden &garden, Population &population, int (&arguments)[10]);
bool search(Garden &garden, Population &population, int (&arguments)[10]);
bool forage(Garden &garden, Population &population, int (&arguments)[10]);
bool take(Garden &garden, Population &population, int (&arguments)[10]); //Species Masters
bool Ant(Garden &garden, Population &population, int (&arguments)[10]);
bool Bee(Garden &garden, Population &population, int (&arguments)[10]);
};

В этих вторичных функциях мы конструируем функции, просто соединяя в цепочки другие задачи:

  • Задача walk — это просто несколько шагов (с обработкой ошибок)
  • Задача take — это задача look и swap (она необходима из-за обработки памяти муравья, которую я объясню позже)
  • Задача idle — это выбор случайного места и движения туда (с помощью walk), ожидание в течение нескольких циклов (с помощью wait) и повторение этого цикла в течение заданного количества раз
  • … и так далее

Другие задачи более сложны. Задача search выполняет запрос к памяти для поиска любых воспоминаний о местах, содержащих объект «пища» (съедобного для данного вида ботов). Она загружает эти воспоминания и обходит их все, «ища» пищу (в случае муравьёв это трава). Если воспоминаний о пище нет, задача заставляет существо случайно бродить по миру и оглядываться. Смотря и изучая (выполняя “look” с viewRadius = 1; т.е. смотря только на тайл под собой), существо может обновлять свою память информацией об окружениях, разумно и целенаправленно ища пищу.

Более обобщённая задача forage состоит из поиска пищи, подбирания это пищи, осматривания (для обновления памяти и поиска пищи по соседству), возврата домой и складирования пищи.

Можно заметить, что муравьи выбираются из муравейника и ищут пищу целенаправленно. Из-за инициализации первоначальный путь муравьёв направлен к случайной точек, потому что их память в t = 0 пуста. Затем им отдаётся приказ подбирать пищу в задаче forage, также они осматриваются, убеждаясь, что пищи уже нет. Время от времени они начинают блуждать, потому что у них заканчиваются места, в которых они видели пищу (зловещая недальновидность).

Каждый вид связан с одной управляющей задачей, задающей всё его поведение: она состоит из каскада всё более мелких задач, с лёгкостью определяемых набором очередей памяти и примитивных задач. И, наконец, у бота есть «вид», определяющий род задаваемого ему ИИ. Это задачи наподобие «Ant» и «Bee».

Структура «сверху вниз»

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

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

class Task{ public: //Members std::stack<Task> queue; bool initFlag = true; int args[10]; bool (Task::*handle)(Garden&, Population&, int (&)[10]); int botID; std::string name; //Constructor Task(std::string taskName, int taskBotID, bool (Task::*taskHandle)(Garden&, Population&, int (&)[10])){ name = taskName; botID = taskBotID; handle = taskHandle; } //Launch a Task bool perform(Garden &garden, Population &population); //Continue with primitives here...

Каждый объект задачи в очереди хранит массив аргументов, который передаёт связанному обработчику функции. Эти аргументы определяют поведение этих примитивных задач, созданных как можно более общими. Аргументы передаются по ссылке, поэтому объект задачи в очереди может хранить свои аргументы и позволять изменять их своим подфункциям, поэтому можно реализовывать такие вещи, как итерации для ожидания в течение определённого количества тактов или запросов на сбор определённого количества предметов, и т.д. Подфункции изменяют значение итератора (argument[n]) родительской функции по ссылке и делают своё условие успеха зависимым от её значения.

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

//Execute Task Function
bool Task::perform(Garden &garden, Population &population){ //Debug Message if(debug){std::cout<<"Bot with ID: "<<botID<<" performing task: "<<name<<std::endl;} //Change the Name and Execute the Task population.bots[botID].task = name; return (*this.*handle)(garden, population, args);
}

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

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

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

//Species Functions
bool Task::Ant(Garden &garden, Population &population, int (&arguments)[10]){ //Initial Condition if(initFlag){ Task forage("Search for Food", botID, &Task::forage); forage.args[0] = population.bots[botID].forage; //What are we looking for? queue.push(forage); initFlag = false; } //Queue Loop if(!queue.empty()){ //Get the Top Task Task newtask = queue.top(); queue.pop(); //If our new Task is not performed successfully if(!newtask.perform(garden, population)){ queue.push(newtask); return false; } //If it was successful, we leave it off return false; } //Return Case for Mastertask initFlag = true; return false;
}

С помощью моего цикла очереди (см. код) я могу многократно выполнять одну функцию и каждый раз выполнять верхний элемент в её очереди, выталкивая из неё элементы, если вызов их метода perform возвращает true.

Результаты

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

//Anthill General Configuration File
debug = true; //World Generation Parameters
seed = 15;
water = true; //Species that the simulation recognizes
Species: { //Ant Species Ant: { masterTask = "Ant"; color = (0, 0, 0); viewDistance = 2; memorySize = 5; forage = 2; trail = true; fly = false; } Bee: { masterTask = "Bee"; color = (240, 210, 30); viewDistance = 4; memorySize = 30; forage = 4; trail = false; fly = true; } Worm: { masterTask = "Bee"; color = (255, 154, 171); viewDistance = 1; memorySize = 5; forage = 3; trail = true; fly = false; }
} Population: ( {species = "Ant"; number = 40;}//, //{species = "Bee"; number = 12;}, //{species = "Worm"; number = 5;}
)

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

Одновременная симуляция 40 муравьёв, собирающих траву. Создаваемые ими в песке пути возникают благодаря повышенному весу, назначаемого «неутоптанной» земле. Это приводит к созданию характерных «муравьиных шоссе». Также их можно интерпретировать как феромоны, но это больше походило бы на правду, если бы муравьи на самом деле обменивались воспоминаниями.

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

Отладка воспоминаний муравьёв

Структура сложных задач и памяти привели к непредусмотренным сложностям и необходимости обработки исключений.

Вот три особенно сложных багов памяти, которые заставили меня переделать подсистемы:

Бегающие по кругу муравьи

Один из первых багов, с которыми мне пришлось столкнуться: муравьи безумно бегали по паттерну, заключённому в квадрате в поисках травы на голой земле. Эта проблема возникла, потому что на тот момент я ещё не реализовал обновление памяти. У муравьёв были воспоминания о местоположении пищи, и как только они подбирали траву и снова осматривались, формировались новые воспоминания.

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

(например, существо видит, что там больше нет травы, но не помнит, что там раньше была трава). Я исправил это следующим образом: данные объекта просто переписываются в старых воспоминаниях, если мы видим то же место и объект при этом изменился. Возможно, в будущем я просто добавлю к воспоминаниям свойство «invalid», чтобы боты могли запоминать старую информацию, которая может быть важной, но больше не действительная информация «проявлялась» («здесь я видел медведя, но теперь его нет»).

Муравьи подбирают предметы под другими муравьями

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

Если он есть, она «обменивается» (swap), а если нет, то она «ждёт» (wait) два хода, чтобы другой муравей точно ушёл с места. Эту проблему я решил, сделав задачу swap примитивной и создав задачу take, которая сначала смотрит на землю, чтобы увидеть, есть ли там предмет. В одном случае это действие на два такта, в другом — на один такт.

Недостижимые локации

Ещё один неприятный баг, заставивший меня переделать обработку памяти, заключался в том, что некоторые места, которые мог видеть муравей, были для него недостижимы. Они возникали из-за моего ленивого размещения «крестиков травы» на суше, которые иногда нависали над водой. Это заставило меня обобщить задачу step.

Если она не была помечена в их памяти (например, булевой переменной «reachable»), то они продолжали воспоминать это и записывать в очередь, пока это действие не оставалось единственным. При передаче запроса на поиск пищи у муравьёв часто возникали воспоминания о местах, до которых они на самом деле не могли добраться (они видели траву над водой и безумно хотели её собрать). Это вызывало сильное торможение, потому что они постоянно выполняли в каждом такте операции поиска пути, пытаясь добраться туда, и терпели неудачу.

Кроме того, задача search выполняет запросы мест с пищей только к достижимым воспоминаниям. Решение заключалось в том, чтобы в задаче step обновлять память, если он не может найти путь к месту, помечая его в памяти как недостижимое.

Система в общем

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

Например, в качестве направления для парсинга действия look используется вверх-вниз и влево-вправо, то есть последнее воспоминание находится в нижнем правом углу. Созданная мной система надёжна не на 100%, и я до сих пор замечаю некоторые артефакты. Особенно это заметно на больших симуляциях, когда, трава растёт быстро и чуть-чуть склоняется в сторону юго-востока вне зависимости от seed. При вспоминании информации для выполнения поиска предметов это означает, что существа будут склонны двигаться на юго-восток.

Улучшения

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

«think» может быть примитивным действием запроса к памяти. В том числе и увеличение надёжности функций обработки памяти, а также добавление новых примитивов, например «think», и производных высокоуровневых задач, например «decide» или «dream». «dream», в свою очередь, может состоять из нескольких вызовов «think»: выбор случайной памяти, получение случайного свойства и многократное повторение для подкрепления частых тем или важных ассоциаций.

На будущее я планирую три конкретных дополнения:

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

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

Таким образом можно передавать информацию, например, расположение пищи или других ресурсов. Общение между сущностями, вероятно, состоит из одной или двух примитивных задач для обмена воспоминаниями или осуществления запросов к воспоминаниям других ботов (например, «say» или «ask»).

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

Будущее

Важнейшей функцией для симуляции сообществ будет добавление групповых структур и наделение этих групп макроуровневыми свойствами, например, их общими «целями и обязанностями». Это даёт нам своего рода «seed», из которого мы можем получать высокоуровневые задачи, которые делегируются вниз по иерархии групповых структур до «нижних» высокоуровневых задач, непосредственно влияющих на мир. Также это позволяет создать форму политической структуры.

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

Кроме того, я могу скомбинировать эту систему с созданными ранее генераторами карт (расширив класс мира), чтобы мир стал более реальным.

В заключение

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

А пока вот видео с пчёлами, ищущими пыльцу в цветах; они закодированы с помощью той же основы. Ждите следующей статьи.

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

… а вот функция-член Bee Task:

bool Task::Bee(Garden &garden, Population &population, int (&arguments)[10]){ //Just Search for Flowers if(initFlag){ //Define our Tasks Task take("Take Food", botID, &Task::take); Task eat("Eat Food", botID, &Task::consume); Task search("Locate Food", botID, &Task::search); search.args[0] = population.bots[botID].forage; queue.push(eat); queue.push(take); queue.push(search); initFlag = false; } //Work off our allocated queue. if(!queue.empty()){ //Get the Top Task Task newtask = queue.top(); queue.pop(); //If our new Task is not performed successfully if(!newtask.perform(garden, population)){ //Put the Task back on queue.push(newtask); } //If it was successful, we leave it off return false; } initFlag = true; return true;
}

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть