Home > Artificial Intelligence > “Counter Strike” Agent-Goal-Labyrinth-Simulation

“Counter Strike” Agent-Goal-Labyrinth-Simulation

What’s the “counter strike” agent-goal-labyrinth-simulation about?
The counter strike agent-goal-labyrith-simulation is one amongst several mini projects students have to solve in the second semester of the master course at the Department of Intelligent Transport Systems at the University of Applied Sciences Technikum Wien. In short it is about agents and goals that get distributed arbitrarily in the discrete environment of a labyrinth. Each agent has to find a way to his corresponding exit and leave the labyrinth – without being seen by other agents. The environment is deterministic and fully observable to the agents, and agent-moves are round based – means each agent can take one step each round. The interesting question is: what to do in case agents end up in a deadlock – blocking each other’s way? I did an reference implementation in Java that addresses this issues for friends that study at the stated University. The implementation can be downloaded at the bottom of the post.

The Labyrinth
The labyrinth has the layout of a x/y grid, in which walls are 1 field thick and walkable areas have the size of 1 field. A given percentage of walls in between the walkable areas then get removed to get corridors an agent can walk along. Important fact: all walkable areas inside the labyrinth are connected, so you can reach every non-wall field from every other non-wall field – there is no “isolated island”. A small demo labyrith is shown below. Walls are displayed as ##, walkable fields as two white spaces.

##########################################
##  ##          ##  ##      ##          ##
##  ##########  ##  ######  ######  ##  ##
##  ##  ##                  ##      ##  ##
##  ##  ##  ##  ##########  ##  ##########
##          ##      ##          ##      ##
##  ##################  ##  ######  ######
##          ##      ##  ##          ##  ##
##  ##########  ##########  ##########  ##
##  ##  ##  ##                          ##
######  ##  ##  ##########  ##########  ##
##              ##      ##  ##          ##
##  ##############  ##############  ######
##      ##                  ##  ##      ##
######  ######  ##############  ##  ##  ##
##          ##          ##      ##  ##  ##
######  ##  ##  ##########  ##############
##  ##  ##          ##      ##          ##
##  ##  ##########  ######  ##  ######  ##
##          ##                      ##  ##
##########################################

The Agents and Goals
An agent that’s in the labyrinth only has 4 possible actions: go up, down, left or right. From the field he’s currently on he can only go to adjacent fields if the field is walkable (e.g. a wall is not walkable). The agent’s field of vision is up/down/left/right – as far as the walls let him see. Fields the agent can look at are observed by the agent. As agents are not allowed to see each other on their way to their exits (this is probably where the “counter strike” in the name comes from), an agent cannot walk on a field that’s observed by another agent.

10 agents and 10 goals get arbitrarily distributed among the labyrinth. Each agent has a corresponding goal, through which he – and only he – can leave the labyrinth, which is his target. The distribution of agents and goals has to be done in a way that agents don’t initially see each other and don’t initially stand on a goal (and of course agents/goals can’t be placed in walls). As the game isn’t multithreaded but round based, each agent can take one step each turn. Then another agent continues with his step, and so on. The labyrinth (including all goals, the position and field of vision of other agents) is fully observable to the agents, and the agents’ actions are deterministic (means if an agent takes a step forward he end’s up being one step forward – except he ran into wall). To the agents the labyrinth is dynamic (as other agents can block an existing way to the goal or free an previously blocked way). The labyrinth with 10 agents and goals placed is shown below. Agents are displayed as an A followed by their number, e.g. A2, goals as the same with G, e.g. G7, with e.g. A0 corresponding to G0.

##########################################
##G2##          ##  ##      ##          ##
##  ##########  ##  ######  ######A2##  ##
##  ##  ##                  ##      ##  ##
##  ##  ##  ##  ##########  ##A5##########
##    A1    ##      ##          ##      ##
##  ##################  ##  ######  ######
##  G7    A3##      ##  ##          ##  ##
##  ##########G6##########  ##########  ##
##  ##  ##  ##            A6            ##
######A9##  ##  ##########  ##########  ##
##              ##      ##  ##          ##
##  ##############G4##############  ######
##      ##                  ##  ##G5    ##
######A0######  ##############  ##  ##  ##
##          ##      A4  ##G3    ##G9##  ##
######  ##  ##  ##########A7##############
##A8##  ##    G1    ##      ##          ##
##  ##  ##########  ######  ##G8######  ##
##          ##          G0          ##  ##
##########################################

The Implementation
The reference implementation uses an A* algorithm and a Manhattan heuristic to estimate the distance to goals. If an agent finds a path to his goal, he takes the first step towards it. As other agents then do their steps, the found path may be invalid when the agent can do his next step – or a better way has probably opened. This is why an agent has to check his path again before taking the next step. For the same reason the D* algorithm would be more efficient than the A* algorithm: the D* calculates the path from the goal to the start and doesn’t have to recalculate the whole path when changes happen to parts of the path. The A* is still applicable as long as the labyrinth is not too big and there aren’t too much agents, as the branching factor isn’t that high (on average something between 1 and 2, with 3 being the absolute maximum). After each iteration of the program, in which each agent took exactly one step, the implementation shows the current state of the labyrinth.

Fields that are currently part of the path of an agent to his goal are marked with a dot ., and fields that are in the field of vision of an agent with an asterisk *. A screenshot of agents A0, A4, A6 having found their way to the goal, while agents A1, A2, A3, A5, A7, A8, A9 are being blocked is shown below.

##########################################
##G2##          ##  ##      ##    *     ##
##  ##########  ##  ######  ######* ##  ##
##  ##  ##                  ##* * A2##  ##
##  ##  ##  ##  ##########  ##* ##########
##* A1* * * ##      ##* * * * A5##      ##
##  ##################  ##  ######  ######
##* G7* A3* ##      ##  ##          ##  ##
##  ##########G6##########  ##########  ##
##  ##A9##  ##. . . . . A6* * * * * * * ##
######* ##  ##  ##########  ##########  ##
##    *         ##      ##  ##          ##
##  ##############G4##############  ######
##    * ##    . . .         ##  ##G5    ##
######* ######. ##############  ##  ##  ##
##* * A0. . ##. . A4* * ##A7* * ##G9##  ##
######* ##. ##  ##########* ##############
##* ##* ##. . G1. . ##    * ##          ##
##A8##* ##########. ######* ##G8######  ##
##*   *     ##    . . . G0*         ##  ##
##########################################

Now the intersting question is: what to do if agents somehow end up in a deadlock situation, where they block each others way? We have to assume that the agents are willing to help each other therefore. In case no agent moves, the agents won’t find a way at all, therefore this approach is not applicable. One could write a suffisticated algorithm which tells the agent where he should walk in case he can’t reach his goal temporarily. This algorithm has to consider a lot of special cases, e.g. the agent being at the end of a blind alley, the goal of another agent being in the field of vision at the start of the alley. Or the agent hiding at a blind alley, hoping to not block any important path with his field of vision.

I’ve used a different approach: coincidence – which is not as bad as it sounds from a statistical point of view. But as using coincidence alone would cause distortion to other agents (e.g. agent that can’t reach his goal blocks path of another agent by change), agents are not allowed to make a move which causes them to block other agents’ paths as long as they don’t have a path themselves. This approach is kind of the easiest version of a penality system for the moves that can be taken: the agents chose the move with the least penalty, and the penaltiy for blocking another agent’s path is so high that this move never gets taken. The penalty system could be extended, e.g. by a penalty for staying at the same position, for the size of the field of vision, for the distance to goals of other agents, for the distance to the own goal etc. With correct combination of the penalty parts, a heuristic for agents without paths would arise – which would make their wandering around more efficient. The video below shows a labyrinth with 10 agents searching for their goal, in which agents that don’t have a path act randomly – without blocking others agents’ paths.

Download
The implementation comes with all needed resources, including some labyrinths in different sizes. You can specify which labyrinth should get used as commandline argument or directly in the Start.java.
Reference Implementation Java Source, md5: 0409ee96eba01eb409684f6519a9cc55, sha1: c886395dc38281b7bfdb7b1d46c3677b0524fb1f.
Reference Implementation Java Binaries, md5: a9e65532d6425acf7287224749abd73e, sha1: 796b14b6d256205af97f6b97320a03cf610b6206.

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: