Geekly Articles each Day
📜 ⬆️ ⬇️

Modular bot ants with memory


One of the projects that I had long dreamed of implementing was modular bots of tasks with memory. The ultimate goal of the project was to create a world with creatures capable of acting independently and collectively.

I used to program worlds generators, so I wanted to populate the world with simple bots that use AI, defining their behavior and interactions. Thus, thanks to the influence of actors on the world, it was possible to increase its detail.

I already implemented the basic task pipeline system for Javascript (because it simplified my life), but I wanted something more reliable and scalable, so I wrote this project in C ++. To this I was encouraged by the competition for the implementation of a procedural garden in the subreddit / r / proceduralgeneration (hence the corresponding topic).
')
In my system, the simulation consists of three components: the world, the population, and the set of actions connecting them. Consequently, I had to create three models, which I will discuss in this article.

To increase the complexity, I wanted the actors to preserve information about previous experiences of interacting with the world and to use knowledge of these interactions in future actions.

When creating a model of the world, I chose a simple path and used Perlin noise to place it on the surface of the water. All other objects in the world were located absolutely randomly.

For the population model (and its “memory”), I simply created a class with several characteristics and coordinates. This was supposed to be a low resolution simulation. Memory is a queue, bots look around, save information about their surroundings, write to the queue and manage this queue as an interpretation of their memory.

For connecting these two systems of actions, I wanted to create a framework of primitive tasks within a hierarchical system of task queues so that individual entities could implement complex behavior in the world.


Sample card. The water took the form of a river quite unintentionally. All other elements are randomly located, including the anthill, which in this seed is shifted too far to the edge (but the river looks beautiful).

I decided that a good test model that guarantees the reliability of the implementation of basic functions (and the task queue system as a whole) and prevents memory leaks (there were a lot of them) would be a bunch of ants in the grass collecting leaves.

I want to describe in more detail the structure of task systems and memory, as well as to show how complexity was created from (mostly) primitive basic functions. I also want to show some funny "memory leaks of ants" that can be encountered when ants start to run insanely in circles in search of grass or stand still and make the program slow down.

General structure


I wrote this simulation in C ++, and for rendering I used SDL2 (I used to write a small presentation class for SLD2). I also used the A * implementation (slightly modified), which I found on github, because my implementation was hopelessly slow, and I could not understand why.

A map is simply a 100 × 100 grid with two layers — a soil layer (used for finding ways) and a fill layer (for performing interaction tasks and finding ways). The world class also handles various cosmetic functions, such as grass and vegetation growth. I am talking about this now, because these are the only parts that will not be described in the article.

Population


The bots were in a class with properties describing a single creature. Some of them were cosmetic, others influenced the performance of actions (for example, the possibility of flight, the range of sight, what it feeds on and what a creature can wear).

The most important are the auxiliary values ​​that determine the behavior. Namely: the vector containing their current path A *, so that it does not need to be recalculated in each cycle (this saves computation time and allows you to simulate more bots), and a memory queue determining the interpretation of the creatures of their environment.

Memory queue


The memory queue is a simple queue containing a set of memory objects limited in size by the bot property. With each addition of new memories, they were pushed forward, and everything that went beyond the borders from behind was cut off. Because of this, some memories could be more “fresh” than others.

If a bot wanted to recall information from memory, then it created a memory object (request) and compared it with the one in memory. The recall function then returned a vector of memories that matched any or all of the criteria specified in the query.

class Memory{ public: //Recall Score int recallScore = 1; //Memory Queryable? Array bool queryable[4] = {false, false, false, false}; //Memory Attributes std::string object; std::string task; Point location; bool reachable;

Memories consist of a simple object containing several properties. These memory properties are considered "associated" with each other. Also, each memory is given a “recallScore” value, which is iterated each time the memory is remembered by the recall function. Each time a bot remembers memories, it sorts in one pass in turn, starting from behind, changing the order of the memories, if the recall of the older memories is higher than that of the new one. Because of this, some memories can be more “important” (with large memory sizes) and last longer within the queue. Over time, they will be superseded by new ones.

Memory queues


I also added several overloaded operators to this class so that you can perform direct comparisons between the memory queue and the query, comparing “any” or “all” properties so that only the specified properties are overwritten when the memory is overwritten. Because of this, we may have an object memory associated with some place, but if we look at this place again and the object is not there, we can update the memory by overwriting it with a memory containing a new fill tile using a query corresponding to this place. .

 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; } } }

In the process of creating the code of this system, I learned a lot.

Task system


The nature of the game's cycle or rendering is that the same functions are repeatedly performed in each clock cycle, but I wanted to implement non-cyclic behavior in my bots.

In this section, I will explain two views on the structure of the task system designed to counteract this effect.

Bottom-up structure


I decided to move from the bottom up and create a set of "primitive actions" that the bots should perform. Each of these actions lasts only one beat. Having a good library of primitive functions, we can combine them into complex actions consisting of several primitive ones.

Examples of such primitive actions:

 //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...

Notice that these actions contain references to both the world and the population, allowing you to change them.


All task functions are members of my task class; after thorough testing, they proved their reliability and ability to combine into more complex tasks.

 //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]); };

In these secondary functions, we construct functions by simply chaining other tasks:


Other tasks are more complex. The search task performs a memory query to search for any memories of places containing the “food” object (edible for this type of bot). She loads these memories and goes around them all, “looking for” food (in the case of ants, this is grass). If there is no memory of food, the task causes the creature to wander around the world and look around. By looking and studying (performing “look” with viewRadius = 1; that is, looking only at the tile underneath), a creature can update its memory with information about its surroundings, reasonably and purposefully searching for food.

The more generalized forage task consists of finding food, picking up food, examining (to refresh memory and find food in the neighborhood), return home and store food.


You can see that the ants are selected from the anthill and are looking for food purposefully. Because of initialization, the initial path of the ants is directed to a random point, because their memory at t = 0 is empty. Then they are given the order to pick up food in the forage task, and they also look around, making sure that there is no food anymore. From time to time they begin to wander, because they run out of places where they saw food (ominous short-sightedness).

And finally, the bot has a “look” that defines the kind of AI it is assigned to. Each type is associated with a single controlling task, which sets all its behavior: it consists of a cascade of ever smaller tasks, easily defined by a set of memory queues and primitive tasks. These are tasks like Ant and Bee.

Top-down structure


If you look from top to bottom, the system consists of the “task-master” class, which coordinates the control tasks and their execution for each individual bot on the map.

Taskmaster has a vector of control tasks, each of which is associated with a bot. Each control task, in turn, has a queue of subtasks that are loaded when the task object is first initialized with a function associated with it.

 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...

Each task object in the queue stores an array of arguments that passes to the associated function handler. These arguments determine the behavior of these primitive tasks, created as general as possible. Arguments are passed by reference, so the task object in the queue can store its arguments and allow its subfunctions to change them, so you can implement such things as iterations to wait for a certain number of ticks or requests to collect a certain number of items, etc. Subfunctions change the iterator value (argument [n]) of the parent function by reference and make its success condition dependent on its value.

At each stroke, the taskmaster goes through the list of control tasks and executes them by calling their perform method. The perform method, in turn, looks at the top queue element inside the task and executes it with the arguments from the task. This way you can cascade down the task queue, always performing the topmost task. Then the return value of the task determines the completion of the task.

 //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); }

When a primitive task returns true, it has reached its stable point, or at least should not be repeated (for example, step returns true when the creature reached the end point). That is, its return condition is satisfied and it is removed from the queue so that the next task can be performed the next task.

A task containing a task queue returns true after the queue is empty. Thanks to this, it is possible to create complex tasks with a queue and sub-queue structure in which the same functions are invoked constantly, but each one-step call iterates the state of the game and the state of the task.

Finally, control tasks use a simple structure — they are called in each cycle, load a task only if they are empty, and otherwise they perform tasks loaded in their turn.

 //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; }

With the help of my queue cycle (see code), I can repeatedly perform one function and each time execute the top element in its queue, pushing elements out of it if the call to their perform method returns true.

results


All this is wrapped in libconfig, so the simulation parameters are very easy to change. You can easily encode many control tasks (I created ants and bees), and defining and loading new species using libconfig is amazingly simple.

 //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;} )

They were elegantly loaded into a simulation. Thanks to a new, improved search for ways, I can simulate a large number of individual active bots collecting food on a two-dimensional plane.


Simultaneous simulation of 40 ants collecting grass. The paths they create in the sand are due to the increased weight assigned to the “non-trampled” ground. This leads to the creation of characteristic "ant highways". They can also be interpreted as pheromones, but it would be more like the truth if ants actually exchanged memories.

The modularity of this system ensures the rapid creation of new species whose behavior is determined by a simple control task. In the code shown above, you can see that I created worms and AI of bees, just by changing their color, the limitations of finding ways (they can't fly), the range of sight, and the size of the memory. At the same time, I changed their general behavior, because all these parameters are used by functions of primitive tasks.

Debugging Ant Memories


The structure of complex tasks and memory led to unforeseen difficulties and the need for exception handling.

Here are three particularly difficult memory bugs that made me redo the subsystems:

Ants running around the circle


One of the first bugs that I had to face: ants ran insanely over a pattern that was enclosed in a square in search of grass on bare ground. This problem arose because at that time I had not yet implemented a memory upgrade. The ants had memories of the location of the food, and as soon as they picked up the grass and looked around again, new memories formed.

The problem was that the new memory was at the same point, but the old one was preserved. This meant that in the process of searching for food, the ants recalled and kept the localities of the food, which were no longer valid, but these old memories remained and supplanted the new ones (they remembered this tasty herb).

I corrected it as follows: the object data is simply rewritten in old memories if we see the same place and the object has changed (for example, the creature sees that there is no more grass, but does not remember that there was grass before). Perhaps in the future I will simply add the “invalid” property to my memories so that the bots can remember old information that may be important, but the actual information no longer “appeared” (“here I saw a bear, but now it isn’t”).

Ants pick up items under other ants.


From time to time (especially when there are a large number of ants and a high density of grass), two ants can get on one grass tile in one measure and try to pick it up. This meant that the first ant entered the tile, looked around and took the object in 3 steps. In turn, the second ant did the same, only right before raising the object, another ant snatched it from under its nose. He calmly continued his tasks, examining the same environment as the other ant in the previous tact, and processed his turn of memory in the same way (because at this stage their memories are identical). This led to the fact that the second ant copied the first one, never picking up objects and following the first one, which actually did all the work. I noticed this, because in the simulation of five ants only three were visible. It took a long time to find the cause.

I solved this problem by making the swap task primitive and creating the take task, which first looks at the ground to see if there is an object there. If it is, it “swaps” (swap), and if not, it “waits” (wait) for two moves for the other ant to just leave the place. In one case it is an action for two measures, in the other - for one measure.

Unreachable locations


Another unpleasant bug that caused me to redo the processing of memory was that some of the places that an ant could see were unattainable for him. They arose because of my lazy placement of "grass crosses" on land, which sometimes hung over the water. This made me summarize the task step.

When sending an inquiry to search for food from ants, they often had memories of places they could not really reach (they saw grass above the water and madly wanted to gather it). If it was not marked in their memory (for example, the “reachable” Boolean variable), then they continued to remember it and write to the queue until this action remained the only one. This caused a strong inhibition, because they constantly carried out the search for a path in each step, trying to get there, and failed .

The solution was to update memory in the step task if it cannot find the path to the place, marking it in memory as unattainable. In addition, the search task fulfills the requests of places with food only to accessible memories.

System in general


In general, I want to say - yes, I regret that I spent the week of my life on a programming marathon, because I was inspired to create bots that do what I tell them (and also what they want to do!). I had to do a few tricks and managed to learn a lot.

The system I created is not 100% reliable, and I still notice some artifacts. For example, as a direction for parsing, the look action is used up-down and left-right, that is, the last memory is in the lower right corner. When recollecting information to perform a HOS, this means that creatures will tend to move southeast. This is especially noticeable in large simulations, when the grass grows quickly and inclines slightly towards the southeast, regardless of the seed.

Improvements


I think that for the simulation of more complex memories of more complex creatures requires significant improvements.

Including increase in reliability of functions of processing of memory, and also adding of new primitives, for example «think», and derivatives of high-level tasks, for example «decide» or «dream». “Think” can be a primitive memory request action. “Dream”, in turn, can consist of several “think” calls: choosing a random memory, obtaining a random property, and repeating it repeatedly to reinforce frequent topics or important associations.

For the future, I plan three specific additions:


Handling interruptions and prioritizing tasks may be necessary for interaction between entities, because a bot cannot blindly continue its activities when communicating with it (it must somehow “listen”) or attack it (“escape” or “fight”) ).

The communication between entities probably consists of one or two primitive tasks for sharing memories or making requests for memories of other bots (for example, “say” or “ask”). In this way, information such as the location of food or other resources can be transmitted.

I hope to realize these tasks and make a graph of the rate of accumulation of resources by a large group with and without communication. The population already tracks the amount of food collected in each cycle. It would be interesting to show that sharing memories can affect performance.

Future


The most important function for simulating communities will be the addition of group structures and endowing these groups with macro-level properties, for example, their common “goals and responsibilities”. This gives us a kind of “seed”, from which we can get high-level tasks, which are delegated down the hierarchy of group structures to “lower” high-level tasks that directly affect the world. It also allows you to create a form of political structure.

Such a system is quite self-sufficient, and the visualization is simply superimposed on top of it. It will be very easy to replace insects with humanoids, gathering resources and storing them in some place so that it grows in size. The nature of the growth of their home can, for example, be very dependent or completely independent of the actions of the bots.Different species may have different tribes with different characteristics and trends.

In addition, I can combine this system with previously created map generators (expanding the world class) to make the world more real.

Finally


In the near future, I plan to replace creatures with people and implement several recent functions. Maybe I will publish the full source code when I improve the quality of the system (in some places the code is rather chaotic).

Wait for the next article. For now, here's a video of bees looking for pollen in flowers; they are encoded using the same framework.


I chose this seed because the starting point is located on a small island. However, the bees are not programmed to return to the hive, but simply constantly collect pollen. You may notice that their range of vision is higher and sometimes they very intentionally move towards the flower that they just saw.

... and here is the Bee Task member function:

 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; }

Source: https://habr.com/ru/post/443252/

More articles:


All Articles