CODEWITHSUNDEEP
machine-learningsimulationcollision-detection
Timo
Timo

Reputation: 9835

Deterministic action collision handling in population simlulations

I'm working on the theoretical framework for my own simulation environment. I want to simulate evolutionary algorithms on populations, but I don't know how to handle conflicting actions between multiple individuals.

The simulation has discrete time steps and takes place on a board (or tile grid) with a random population of different individuals. Each individual has some inputs, internal state and a list of possible actions to take each step. For example, an individual can read its position on the grid (input) and move one tile in a certain direction (action). Now, lets say I have two individuals A and B. Both perform a certain action during the same simulation step which would result in both individuals ending up on the same tile. This, however, is forbidden by the rules of the environment.

In more abstract terms: my simulation is in a valid state S1. Due to independent actions taken by multiple individuals, the next state S2 (after one simulation step) would be an invalid state.

How does one resolve these conflicts / collisions so I never end up in an invalid state?

I want the simulation to be replayable so the behavior should be deterministic.

Another question is fairness. Lets say I resolve conflicts by whoever comes first passes. Because, in theory, all actions happen at the same time (discrete time steps), "whoever comes first" isn't a measurement of time but data layout. Individuals that are processed earlier now have an advantage because they happen to be in favorable locations in the internal data structures (i.e. lower index in the array).

Is there a way to guarantee fairness? If not, how can I reduce unfairness?

I know these are very broad questions but since I haven't worked out all the constraints and rules of the simulation I wanted to get an overview of what's even possible, or perhaps common practice in these systems. I'm happy about any pointers for further research.

Upvotes: 0

Views: 118

Answers (2)

S_Bersier
S_Bersier

Reputation: 1146

The question is overwhelmingly broad but here is my answer for the following case:

  1. Agents move on a square (grid) board with cyclic boundaries conditions
  2. Possible moves are: a) stay where you are, b) move to one of the 9 adjacent positions The possible moves are assigned a probability
  3. Conflicts will happen for every cell targeted by two agents since we assume no two agents can occupy the same cell (exclusion). We'll solve the conflict by re-rolling the dice until we obtain no conflict.

The general idea:

  1. Roll the dices for every agent i --> targeted cell by agent i

  2. Any two agents targeting the same cell ?

    if yes:

       for every pair of conflicting agents:

       re-roll the dice for BOTH agents

    Notes:

    a) Conflicts are detected when an agent is missing because it has been "crushed" by an other agent (because of relative positions in agents' list).

    b) Here, I assume that re-rolling the dice for both is a "fair" treatment since no arbitrary decision has to be taken.

  3. Did it solve the problem? If not, go back to 2)

  4. Move the agents to the new positions and go back to 1)

I provide a python program. No fancy graphics. Runs in a terminal. The default parameters are:

Board_size = 4

Nb_of_agents=8 (50 % occupation)

If you want to see how it scales with problem size, then put VERBOSE=False otherwise you'll be flooded with output. Note: -1 means an empty cell.

EXAMPLES OF OUTPUT:
Note: I used a pretty high occupancies (50% and 25%) for 
examples 1 and 2. Much lower occupancies will result in 
no conflict most of the time.

##################################################################
EXAMPLE 1: 
VERBOSE=True
Board = 4 x 4
Nb. of agents: 8 (occupation 50%)
==============================================================
Turn:  0
Old board:
[[-1.  7.  3.  0.]
 [ 6. -1.  4.  2.]
 [-1. -1.  5. -1.]
 [-1.  1. -1. -1.]]
Proposed new board:
[[ 1. -1. -1. -1.]
 [-1.  4. -1. -1.]
 [-1.  6. -1.  2.]
 [-1.  7.  5. -1.]]
# of conflicts to solve:  2
Conflicts to solve: [agent_a, agent_b, targeted cell]: 
[0, 1, array([0, 0])]
[3, 5, array([2, 3])]
Proposed new board:
[[-1. -1.  1.  3.]
 [-1.  4. -1.  5.]
 [-1.  6. -1.  2.]
 [-1.  7. -1.  0.]]
No conflicts
<<< OUTPUT >>>
Old board:
[[-1.  7.  3.  0.]
 [ 6. -1.  4.  2.]
 [-1. -1.  5. -1.]
 [-1.  1. -1. -1.]]

Definitive new board:
[[-1. -1.  1.  3.]
 [-1.  4. -1.  5.]
 [-1.  6. -1.  2.]
 [-1.  7. -1.  0.]]
==============================================================
Turn:  1
Old board:
[[-1. -1.  1.  3.]
 [-1.  4. -1.  5.]
 [-1.  6. -1.  2.]
 [-1.  7. -1.  0.]]
Proposed new board:
[[ 3. -1. -1. -1.]
 [ 5. -1.  4. -1.]
 [ 7. -1. -1. -1.]
 [ 6.  1. -1.  2.]]
# of conflicts to solve:  1
Conflicts to solve: [agent_a, agent_b, targeted cell]: 
[0, 6, array([0, 3])]
Proposed new board:
[[ 3. -1. -1. -1.]
 [ 5. -1.  4. -1.]
 [ 7. -1. -1. -1.]
 [-1.  6. -1.  2.]]
# of conflicts to solve:  2
Conflicts to solve: [agent_a, agent_b, targeted cell]: 
[0, 7, array([0, 2])]
[1, 6, array([1, 3])]
Proposed new board:
[[ 3.  1. -1. -1.]
 [ 5. -1.  4. -1.]
 [ 0.  7. -1. -1.]
 [ 6. -1. -1.  2.]]
No conflicts
<<< OUTPUT >>>
Old board:
[[-1. -1.  1.  3.]
 [-1.  4. -1.  5.]
 [-1.  6. -1.  2.]
 [-1.  7. -1.  0.]]

Definitive new board:
[[ 3.  1. -1. -1.]
 [ 5. -1.  4. -1.]
 [ 0.  7. -1. -1.]
 [ 6. -1. -1.  2.]]
==============================================================

##################################################################
EXAMPLE 2:
VERBOSE=False
Board = 200 x 200
Nb. of agents: 10000 (occupation 25%)
==============================================================
Turn:  0
# of conflicts to solve:  994
# of conflicts to solve:  347
# of conflicts to solve:  137
# of conflicts to solve:  63
# of conflicts to solve:  24
# of conflicts to solve:  10
# of conflicts to solve:  6
# of conflicts to solve:  4
# of conflicts to solve:  2
No conflicts
==============================================================
Turn:  1
# of conflicts to solve:  1002
# of conflicts to solve:  379
# of conflicts to solve:  150
# of conflicts to solve:  62
# of conflicts to solve:  27
# of conflicts to solve:  9
# of conflicts to solve:  2
No conflicts
==============================================================

The program (in python):

#!/usr/bin/env python
# coding: utf-8

import numpy
import numpy as np

np.random.seed(1) # will reproduce the examples
# Verbose: if True: show the boards (ok for small boards)
Verbose=True 
# max nb of turns
MaxTurns=2

Board_size= 4
Nb_of_cells=Board_size**2
Nb_of_agents=8 # should be < Board_size**2

agent_health=np.ones(Nb_of_agents)     # Example 1:  All agents move (see function choose_move)
#agent_health=np.random.rand(Nb_of_agents) # With this: the probability of moving is given by health
#agent_health=0.8*np.ones(Nb_of_agents) # With this: 80% of the time they move, 20% the stay in place

possible_moves=np.array([[0,0], [-1,-1],[-1, 0],[-1,+1], [ 0,-1], [ 0,+1], [+1,-1],[+1, 0],[+1,+1]])
Nb_of_possible_moves=len(possible_moves)

def choose_move(agent, health):
    # Each agent chooses randomly a move among the possible moves 
    # with a mobility proportional to health. 
    
    prob[0]=1-agent_health[agent] # low health --> low mobility
    prob[1:9]=(1-prob[0])/8
    move=np.random.choice(Nb_of_possible_moves,1,p=prob)
    return move

def identify_conflicts_to_solve(missing_agents, Nb_of_agents, Old_X, Old_Y):
    # 1) Identify conflicts to solve:
    target_A=[]
    target_B=[]
    [target_A.append([a,(Old_X[a]+possible_moves[move[a]][0])%Board_size, (Old_Y[a]+possible_moves[move[a]][1])%Board_size]) for a in missing_agents];
    [target_B.append([a,(Old_X[a]+possible_moves[move[a]][0])%Board_size, (Old_Y[a]+possible_moves[move[a]][1])%Board_size]) for a in range(Nb_of_agents) if not a in missing_agents];
    target_A=np.array(target_A)
    target_B=np.array(target_B)
    conflicts_to_solve=[]
    for m in range(len(target_A)):
        for opponent in range(len(target_B[:,0])): 
            if all(target_A[m,1:3] == target_B[opponent,1:3]): # they target the same cell
                conflicts_to_solve.append([target_A[m,0], target_B[opponent,0], target_A[m,1:3]])

    return conflicts_to_solve

# Fill the board with -1 (-1 meaning: empty cell)
Old_Board=-np.ones(len(np.arange(0,Board_size**2))) 

# Choose a cell on the board for each agent:
# position = index of the occupied cell
Old_indices = np.random.choice(Nb_of_cells, size=Nb_of_agents, replace=False) 
# We populate the board
for i in range(Nb_of_agents):
    Old_Board[Old_indices[i]]=i
New_Board=Old_Board 


# Coordinates: We assume a cyclic board
Old_X=np.array([Old_indices[i] % Board_size for i in range(len(Old_indices))]) # X position of cell i 
Old_Y=np.array([Old_indices[i] // Board_size for i in range(len(Old_indices))])# Y position of cell i

# Define other properties

move=np.zeros(Nb_of_agents,dtype=int)
prob=np.zeros(Nb_of_possible_moves)

print('==============================================================')
for turn in range(MaxTurns):
    print("Turn: ",turn)
    if Verbose:
        print('Old board:')
        print(New_Board.reshape(Board_size,Board_size))
    Nb_of_occupied_cells_before_the_move=len(Old_Board[Old_Board>-1])
    Legal_move=False
    while not Legal_move:

        for i in range(0,Nb_of_agents):
            move[i]=choose_move(agent=i, health=agent_health[i])
                   
        conflicts_to_solve=-1
        while conflicts_to_solve!=[]:
            # New coordinates (with cyclic boundary conditions):
            New_X=np.array([(Old_X[i]+possible_moves[move[i]][0]) % Board_size for i in range(Nb_of_agents)])
            New_Y=np.array([(Old_Y[i]+possible_moves[move[i]][1]) % Board_size for i in range(Nb_of_agents)])

            # New board
            New_indices=New_Y*Board_size+New_X
            New_Board=-np.ones(Board_size**2) # fill the board with -1 (-1 meaning: empty cell)       
            for i in range(Nb_of_agents): # Populate new board
                New_Board[New_indices[i]]=i        

            # Look for missing agents: an agent is missing if it has been "overwritten" by another agent,
            # indicating conflicts in reaching a particular cell
            missing_agents=[agent for agent in range(Nb_of_agents) if not agent in New_Board]            
            # 1) identify conflicts to solve:
            conflicts_to_solve = identify_conflicts_to_solve(missing_agents, Nb_of_agents, Old_X, Old_Y)
            if Verbose:
                print('Proposed new board:')
                print(New_Board.reshape(Board_size,Board_size))
            if len(conflicts_to_solve)>0:
                print("# of conflicts to solve: ", len(conflicts_to_solve))
                if Verbose:
                    print('Conflicts to solve: [agent_a, agent_b, targeted cell]: ')
                    for c in conflicts_to_solve:
                        print(c)
            else:
                print("No conflicts")
                
            # 2) Solve conflicts
            # The way we solve conflicting agents is "fair" since we re-roll the dice for all of them
            # Without making arbitrary decisions
            for c in conflicts_to_solve:
                # re-choose a move for "a"
                move[c[0]]=choose_move(c[0], agent_health[c[0]])
                # re-choose a move for "b"
                move[c[1]]=choose_move(c[1], agent_health[c[1]])
                 
            

            
        Nb_of_occupied_cells_after_the_move=len(New_Board[New_Board>-1])

        Legal_move = Nb_of_occupied_cells_before_the_move == Nb_of_occupied_cells_after_the_move
        if not Legal_move:
            # Note: in principle, it should never happen but,
            # better to check than being sorry...
            print("Problem: Illegal move")
            Turn=MaxTurns
            # We stop there
    if Verbose:
        print("<<< OUTPUT >>>")
        print("Old board:")
        print(Old_Board.reshape(Board_size,Board_size))
        print()
        print("Definitive new board:")
        print(New_Board.reshape(Board_size,Board_size))
    print('==============================================================')

    Old_X=New_X
    Old_Y=New_Y
    Old_indices=New_indices
    Old_Board=New_Board

Upvotes: 1

sply88
sply88

Reputation: 893

Due to the "independent actions taken by multiple individuals" I suppose there is no way to avoid potential collisions and hence you need some mechanism for resolving those.

A fair version of your "whoever comes first" approach could involve shuffling the individuals randomly at the beginning of each time step, e.g. choose a new and random processing order for you individuals in each time step. If you fix the random seed the simulation results would still be deterministic.

If the individuals aquire some type of score / fitness during the simulation this could also be used to resolve conflicts. E.g. conflict is always won by whoever has the highest fitness (you would need an additional rule for ties then).
Or choose a random winner with winning probability proportional to fitness: If individuals 1 and 2 have fitness f1 and f2, then the probability of 1 winning would be f1/(f1+f2) and the probability of 2 winning would be f2/(f1+f2). Ties (f1 = f2) would also be resolved automatically.
I guess those fitness based rules could be called fair, as long as

  1. Every individual has the same starting fitness (or starting fitness is also set randomly)
  2. Every individual has the same chance of aquiring a high fitness, e.g. all starting positions have the same outlook or starting positions are set randomly

Upvotes: 1

Related Questions