# Simulation

Back to: PRE2015_2_Groep1

## Simulation

In toplevel simulation some of the process of creating this simulation is described. However, as written at the end of that page, since path finding trough ant colony algorithms needs a graph representation of the world, we've decided to alter our approach and only use an ant colony algorithm for assigning robots to piles. For the path finding we now use a heuristic algorithm.

The entire behaviour of the robots can be described by states as follows: There are three states:

- Searching
- The robot tries to go in a straight line
- Whenever that's not possible it chooses a random direction to go in
- Whenever a pile is in sight, it is added to the blackboard (if it isn't already on it, or the point that is on it isn't in sight) and the robot goes to the pile
- Whenever a new element is added to the blackboard all searching robots will re-evaluate whether they want to keep searching or want to go foraging

- Foraging
- The robot tries to go in a straight line towards its goal
- Whenever that's not possible it tries to continue travelling in its previous direction
- Whenever that's not possible it will choose left or right at random and then take the minimum divergence from the straight line towards its goal in that direction
- Whenever the pile it is heading for is cleared it decides by chance whether it will go to another pile or go searching
- If the parameter goalSwitch is set to 2, whenever a pile is in sight, the robot goes to that pile

- Returning
- If a local message is received it tries to follow up on that message. If no message is received:
- The robot tries to go in a straight line towards the Clear Zone
- Whenever that's not possible choose left or right and go into that direction (deviating from the straight line towards the goal as little as possible)
- Also send a local message to all near robots that are returning to the CZ to go into that direction

Comment: It would have been better if in the Returning state, as a priority over the random option, the robot would first try to continue in its previous direction, since that would prevent erratic behaviour of going back and forth. This was originally meant (the returning algorithm should mostly be the algorithm for Foraging with a few adjustments for local messages) but reviewing our code, this appears to be missing. We will put a correction of this in our recommendations.

When a robot is at the clear zone (CZ), it drops whatever it is carrying and decides whether it will go searching or foraging. This choice is made by chance and the probability of it going to Foraging is given by the parameter searchChoice, which is a function of both the size of the blackboard (i.e. the number of coordinates in the blackboard) and the total number of robots. We will elaborate our choice for this parameter in the various simulations later in this article.

If a robot is send to go foraging (rescuing), it is assigned a pile from the blackboard by chance. The chance of choosing blackboard element x is given by:

[math]\displaystyle{ ((\text{the pheromones at }x)\cdot(\text{the treshold depending on the size of the blackboard}))^l \cdot (\text{a function of the distance between the robot and }x) \text{divided by the sum of that expression for all x on the blackboard} }[/math]

where the function of the distance the parameter distance2 if the robot is at the CZ, or distance1 otherwise. If the function of the distance is constantly 1, and the treshold is constant in the size of the blackboard, this coincides with the probability in Media:Liu,_Chen,_Wang_-_2013_-_A_Model_of_Rescue_Task_in_Swarm_Robots_System.pdf.

The following code makes up the simulation. Runnable versions and settings files can be found in media:Total_simulation.zip. Note that the doc-strings aren't entirely accurate. This is because we decided that it would be more useful to write the full documentation on this wiki. The easiest way of running both the simulation (with and without graphics) and the script for processing the data is to install a package containing both python 2.7.x and matplotlib and then installing pygame to that. The package we used was anaconda (see https://www.continuum.io/downloads), in which I installed pygame by typing "conda install -c https://conda.anaconda.org/krisvanneste pygame" (as described in https://anaconda.org/krisvanneste/pygame) into command prompt. If you don't need to see the graphics, you don't have to install pygame (note that I can't guaranty the safety of using the aforementioned method of installing pygame). The simulation, as shown at our presentation can be viewed at https://goo.gl/photos/xCoAm1C48F3FVqD97 (since this wiki doesn't allow files larger than 10 mb). For running the simulation trough the scripts in .zip file, just run the settings file that contains the settings you want to use (n.b. the settings file should contain quite an elaborate block for the

if __name__=="__main__"

statement for the final version of the simulation, so e.g. settings1.py will work, but settings.py is just the choice of parameters we used for the simulation during the presentation). However, the "simulation 1 final (with USE) - plaatjes.py" file is still in the old format and requires a separate "settings.py" file. It can be run by running "simulation 1 final (with USE) - plaatjes.py". This inconsistency is due to the need for running many simulations with different settings on different computers simultaneously, which made it more practical to move the actual running of things to the settings file.

"""the simulation actually used for running over and over again. All graphics stuff has been either commented out or deleted for efficiency""" #todo add parameters for ethical choices import random import math #import multiprocessing #import pygame #from pygame.locals import * #import pygame.font #pygame.init() #this kinda sucks if we don't actually use the graphics but soit #pygame.font.init() extremeDebug=False debug=False def distance(a,b): return sum( [(a[i]-b[i])**2 for i in range(len(a))])**.5 def distanceq(a,b): return sum( [(a[i]-b[i])**2 for i in range(len(a))]) class AO(object): """Represents area of operation""" size = None obstacles = None piles = None robotsInAO = None blackboard =None CZ=None l=2#the "sensitivity of the choice process" speed=1 def __init__(self, size, cz, nRobots, piles, obstacles, evaporatePile = lambda x:x, dropPile = lambda x,y,z:y+1, treshold = lambda x: 1, l=2, searchChoice = lambda bblen, nrob: min((10.*bblen)/(2*nrob),1), distance1 = lambda x: 1/(x+1), distance2 = lambda x: 1, speed=1, goalSwitch=0): """ needs as input: -the size of the AO -the coordinates for the CZ (just one point for now) -the number of robots -a list of piles two points per pile giving two corners of the pile which is assumed to be rectangular (possibly degenerated) a list of objects as ints indicating the number of robots needed to move the object the number of people trapped e.g. [ ((1,2), (3,4), [1,1,6,3,1],5), ((6,7), (8,12), [3,1,1,3,4],0)] -a list of obstacles two points per obstacle giving two corners of the obstacle which is assumed to be rectangular (possibly degenerated) e.g. [((1,1),(2,2)), ((3,1),(4,3))] -a function that determines the speed of evaporation of the pheromones for the piles (mapping floats to floats in a suitable manner) -a function that determines the speed of evaporation of the pheromones for the paths (mapping floats to floats in a suitable manner) -a function called by a robot to increase the pheromone concentration at a pile (three arguments: pilesize, pheromone concentration, treshold) -a function called by a robot to increase the pheromone concentration at a path (to floats) - goalSwitch: if 0, don't try to go to near piles if goal, but don't avoid getting into the wrong pile either if 1, explicitly don't want to get into the wrong pile if 2, whenever a pile - possibly other than the goal pile - is in sight, go to that pile """ self.l=l#the "sensitivity of the choice process" self.speed=speed self.size = (int(size[0]),int(size[1])) #automatically checks for right type this way self.CZ=(int(cz[0]),int(cz[1])) self.__evaporatePile=evaporatePile self.__dropPile=dropPile self.treshold = treshold self.searchChoice = searchChoice #for i in range(nRobots): #self.robotsInAO.append(Robot(self.CZ,self.__drop))#fill the list with robots #want to fill the list of robots one at a time so they don't all live at the same time self.numrobots=nRobots self.researchData={} self.goalSwitch=goalSwitch self.distance1 = distance1 self.distance2 = distance2 self.piles=[] pileID=0 for pile in piles:#create all the piles according to input pileID+=1 x1=int(min(pile[0][0],pile[1][0])) x2=int(max(pile[0][0],pile[1][0])) y1=int(min(pile[0][1],pile[1][1])) y2=int(max(pile[0][1],pile[1][1])) self.piles.append( Pile( self, pileID, (x1,y1), (x2,y2), [int(obj) for obj in pile[2]], pile[3] )) self.researchData[pileID]=[{"size":sum(pile[2]),"robotsAtPile":0}] self.obstacles = [] self.researchData["total size"]=[sum([pile.pileSize() for pile in self.piles])] self.researchData["total victims"]=[sum([pile.pileVictims() for pile in self.piles])] #if extremeDebug: self.obstaclePoints=[] for obstacle in obstacles: #all obstacles are assumed to be rectangles x1=int(min(obstacle[0][0],obstacle[1][0])) x2=int(max(obstacle[0][0],obstacle[1][0])) y1=int(min(obstacle[0][1],obstacle[1][1])) y2=int(max(obstacle[0][1],obstacle[1][1])) self.obstacles.append(( (x1,y1), (x2,y2), ((x2-x1)/2,(y2-y1)/2), (max(distance( ((x2-x1)/2,(y2-y1)/2),(x1,y1)), distance( ((x2-x1)/2,(y2-y1)/2),(x2,y2)))+self.speed)**2 )) # if extremeDebug: # for a in range(x1, x2+1): # for b in range(y1, y2+1): # self.obstaclePoints.append((a,b)) self.robotsInAO = [] self.blackboard = [] self.researchData["blackboard"]=dict(bbelem) for bbelem in self.blackboard#have to copy it because otherwise the data will be synchronised self.precircle = [(n, m) for n in range(-self.speed, self.speed+1) for m in range(-self.speed, self.speed+1) if n*n + m*m <= self.speed*self.speed] def update(self): if self.numrobots>0:#release robots one at a time self.robotsInAO.append(Robot(self, self.CZ, self.speed, self.__dropPile, self.treshold, self.searchChoice, self.distance1, self.distance2)) self.numrobots-=1 bblen=len(self.blackboard) for robot in self.robotsInAO: robot.update() for pile in self.piles: if min(pile.coordinates[0][0],pile.coordinates[1][0])<=robot.coordinates[0]<=max(pile.coordinates[0][0],pile.coordinates[1][0]) and \ min(pile.coordinates[0][1],pile.coordinates[1][1])<=robot.coordinates[1]<=max(pile.coordinates[0][1],pile.coordinates[1][1]): #the robot has arrived at the pile pile.update(robot, self) if len(self.blackboard)>bblen: for robot in self.robotsInAO: robot.setForage() #makes a portion of the searching robots go foraging #now do evaporation: for bbelem in self.blackboard: bbelem["pheromones"]= self.__evaporatePile(bbelem["pheromones"]) if debug: czlen= len([robot for robot in self.robotsInAO if robot.coordinates==self.CZ]) if czlen>0: print czlen for pile in self.piles: self.researchData[pile.id].append({"size":pile.pileSize(), "robotsAtPile":pile.totalRobots()}) self.researchData["blackboard"].append([dict(bbelem) for bbelem in self.blackboard]) self.researchData["total size"].append(sum([pile.pileSize() for pile in self.piles])) self.researchData["total victims"].append(sum([pile.pileVictims() for pile in self.piles])) return len(self.piles)#this will be the check for the main loop def removePile(self, pile): pile.dropRobots() self.piles.remove(pile) toBeRemoved=[] for bbelem in self.blackboard: if pile.isAt((bbelem["coordinates"],)): toBeRemoved.append(bbelem) print "one bb element removed" if not toBeRemoved: "print no bb element removed" self.blackboard=[bbelem for bbelem in self.blackboard if not bbelem in toBeRemoved] def totalRobots(self): return len(self.robotsInAO)+sum([pile.totalRobots() for pile in self.piles]) #def allowedMove(self, coordinates1, coordinates2): # """Decides wether moving from coordinates1 to coordinates2 is possible""" # #a move is possible if there is no obstacle intersecting with [coordinates1, coordinates2] and also no other pile than that at coordinates2 is intersecting with [coordinates1, coordinates2] # length = ((coordinates2[0]-coordinates1[0])**2+(coordinates2[1]-coordinates1[1])**2)**.5 # direction = (float(coordinates2[0]-coordinates1[0])/length, # float(coordinates2[1]-coordinates1[1])/length) # line=[(round(coordinates1[0] + .1*n*direction[0]),round(coordinates1[1]+.1*n*direction[1])) for n in range(round(10*length)+1)] #isn't practical def onALine(self, x, y, z): try: lefthand = ((z[0]-x[0])/distance(z,x), (z[1]-x[1])/distance(z,x)) righthandp = ((y[0]-x[0])/distance(y,x), (y[1]-x[1])/distance(y,x)) righthandm = (-righthandp[0], -righthandp[1]) return min(distance(lefthand, righthandp), distance(lefthand, righthandm))<.01 except ZeroDivisionError: return True #finetuning: due to rounding off in floatingpoint arithmetic we're forced to use a small number for comaparisson. This might need finetuning def getMovements(self,coordinates): #coordinates=(int(coordinatess[0]),int(coordinatess[1]))#not needed circle=[(coordinates[0]+p[0],coordinates[1]+p[1]) for p in self.precircle if 0<=coordinates[0]+p[0]<=self.size[0] and 0<=coordinates[1]+p[1]<=self.size[1]] #circle around the point freeSpace = list(circle) #pilepoints=[] #shaddow=[] speed=self.speed Distance = distance onALine = self.onALine #possibleObstacles = [obstacle # for obstacle in self.obstacles # if distanceq(obstacle[2],coordinates)<=obstacle[3]+1] possibleObstacles = [obstacle for obstacle in self.obstacles if obstacle[0][0]-speed <= coordinates[0] <= obstacle[1][0]+speed\ and obstacle[0][1]-speed <= coordinates[1] <= obstacle[1][1]+speed] #for coord in freeSpace: #remove all points where there are obstacles #for obstacle in possibleObstacles: # if obstacle[0][0]<=coord[0]<=obstacle[1][0] and \ # obstacle[0][1]<=coord[1]<=obstacle[1][1]: # #freeSpace.remove(coord) # obstaclepoints.append(coord) # if extremeDebug: print "trew away " + str(coord) obstaclepoints =[coord for coord in freeSpace for obstacle in possibleObstacles if obstacle[0][0]<=coord[0]<=obstacle[1][0]\ and obstacle[0][1]<=coord[1]<=obstacle[1][1]] #if extremeDebug: print str(obstaclepoints) freeSpace = [coord for coord in freeSpace if not coord in obstaclepoints] if len(freeSpace)!=len(circle): #for coord in freeSpace: # for obst in obstaclepoints: # if self.onALine(coordinates, obst, coord) \ # and Distance(coordinates, obst)<Distance(coordinates, coord): # shaddow.append(coord) shaddow=[coord for coord in freeSpace for obst in obstaclepoints if onALine(coordinates, obst, coord)\ and Distance(coordinates, obst)<Distance(coordinates, coord)] freeSpace = [coord for coord in freeSpace if not coord in shaddow] #possiblePiles = [pile # for pile in self.piles # if distanceq(pile.centre, coordinates)<=pile.radius+1] possiblePiles = [pile for pile in self.piles if pile.coordinates[0][0]-speed <= coordinates[0] <= pile.coordinates[1][0] + speed\ and pile.coordinates[0][1]-speed <= coordinates[1] <= pile.coordinates[1][1] + speed] #for coord in freeSpace: # for pile in possiblePiles: # if pile.coordinates[0][0]<=coord[0]<=pile.coordinates[1][0] and \ # pile.coordinates[0][1]<=coord[1]<=pile.coordinates[1][1]: # pilepoints.append(coord) pilepoints=[coord for coord in freeSpace for pile in possiblePiles if pile.coordinates[0][0]<=coord[0]<=pile.coordinates[1][0]\ and pile.coordinates[0][1]<=coord[1]<=pile.coordinates[1][1]] if extremeDebug: print [pt for pt in freeSpace if pt in obstaclepoints] return [freeSpace, pilepoints, circle] #n.b. this way a robot might go to a pile unintendedly def getPileSizeAt(self, coordinates): """returns the pile size of the pile at the coordinates""" for pile in self.piles: if min(pile.coordinates[0][0],pile.coordinates[1][0])<=coordinates[0]<=max(pile.coordinates[0][0],pile.coordinates[1][0]) and \ min(pile.coordinates[0][1],pile.coordinates[1][1])<=coordinates[1]<=max(pile.coordinates[0][1],pile.coordinates[1][1]): return pile.pileSize() return None def getVictimsAt(self,coordinates): for pile in self.piles: if pile.coordinates[0][0] <= coordinates[0] <= pile.coordinates[1][0] and\ pile.coordinates[0][1] <= coordinates[1] <= pile.coordinates[1][1]: return pile.pileVictims() def pilesAt(self, coordinateList): return list(set([pile for pile in self.piles if pile.isAt(coordinateList)])) #set filters out duplicates def sendLocalMessage(self, centre, radius, message, pileID): for robot in self.robotsInAO: if robot.distance(robot.coordinates, centre)<=radius: robot.setLocalMessage(message, pileID) class Pile(object): objects=None coordinates = None __que = None id=0 def __init__(self,ao,pileID,coordinate1, coordinate2, objects, humans): #all piles are assumed to be rectangles self.objects=[obj for obj in objects] self.__que=[] self.coordinates = (coordinate1, coordinate2) self.id=pileID self.ao=ao self.centre = ((coordinate2[0]-coordinate1[0])/2, (coordinate2[1]-coordinate1[1])/2) self.radius = (max(distance(self.centre, coordinate1), distance(self.centre, coordinate2))+ao.speed)**2 self.humans=humans#the number of humans trapped at the pile def update(self, robot, ao): self.__que.append(ao.robotsInAO.pop(ao.robotsInAO.index(robot))) try: if len(self.__que)>=self.objects[0]: obj=self.objects.pop(0)#remove the object and get the number of needed robots for i in range(obj): rob = self.__que.pop()#remove a robot from the que rob.carrying = True #tell that robot it is carrying an object rob.sendToCZ(self.id)#send that robot to the clear zone self.ao.robotsInAO.append(rob)#add that robot to the list of the AO if len(self.objects)==0: self.ao.removePile(self)#if the pile is empty, remove it from the list of piles except IndexError: self.ao.removePile(self) def totalRobots(self): return len(self.__que) def pileSize(self): return sum(self.objects) def pileVictims(self): return self.humans def dropRobots(self): for robot in self.__que: robot.carrying = True robot.sendToCZ(self.id) self.ao.robotsInAO.append(robot) self.__que=[] def isAt(self, coordinateList): ret=False for coordinates in coordinateList: if min(self.coordinates[0][0],self.coordinates[1][0])<=coordinates[0]<=max(self.coordinates[0][0],self.coordinates[1][0]) and \ min(self.coordinates[0][1],self.coordinates[1][1])<=coordinates[1]<=max(self.coordinates[0][1],self.coordinates[1][1]): ret = True return ret class Robot(object): coordinates=None __previousCoordinates=None direction=None #Robots are assumed to be small enough to be well represented by a single coordinate and even so small that multiple robots can be in the same spot __goal=None __task=None carrying=False ao=None __localMessage=None __lastID=None def __init__(self,ao, coordinates, speed, dropPile, treshold, searchChoice, distance1, distance2): self.coordinates=(int(coordinates[0]),int(coordinates[1])) self.__previousCoordinates=self.coordinates self.__dropPile = dropPile self.treshold = treshold self.searchChoice=searchChoice self.ao= ao self.speed = speed self.distance1=distance1 self.distance2=distance2 def sendToCZ(self, pileID): self.__lastID = pileID self.__goal = self.ao.CZ self.__task="Return" #last coordinate was at the pile, so for simplicity assume it is still there def pickCoordinates(self, target, options): """ input: the floating point coordinates the robot wants to go to output: integer coordinates in option that according to a combination of ceiling and floor correspond to target, or none if none exist """ rounders=[math.floor, math.ceil] targets=[(int(fun1(target[0])),int(fun2(target[1]))) for fun1 in rounders for fun2 in rounders] targets=[e for e in targets if e in options] if not targets: return None #return targets[0] return min(targets, key=lambda x: self.distance(x,target))#take the one closest to the original target def distance(self,a, b): return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**.5 def pickDirection(self,goal, coord): dist = self.distance(goal,coord) if dist >= self.speed: return (coord[0] + self.speed*(goal[0]-coord[0])/dist, coord[1] + self.speed*(goal[1]-coord[1])/dist) else: return goal def chooseRandomDirection(self, options): return random.choice( [point for point in options if self.distance(point, self.coordinates)>=self.speed-2 ]) def setLocalMessage(self, coordinates, pileID): if pileID==self.__lastID: self.__localMessage = coordinates def setForage(self): if random.random()<self.searchChoice(len(self.ao.blackboard), self.ao.totalRobots()) and self.__task=="Search": self.__task="Forage" rnum = random.random() denominator = sum([((pile["pheromones"]+self.treshold(len(self.ao.blackboard)))**self.ao.l)*self.distance1(distance(self.coordinates,pile["coordinates"])) for pile in self.ao.blackboard]) treshold = 0 for pile in self.ao.blackboard: treshold += ((pile["pheromones"] + self.treshold(len(self.ao.blackboard)))**self.ao.l)*self.distance1(distance(self.coordinates, pile["coordinates"])) if rnum<treshold/denominator: self.__goal = pile["coordinates"] break def update(self): Distance=distance if extremeDebug: print "new update" if self.coordinates == self.ao.CZ: self.carrying = False #assign a task and if needed a pile and a path rnum = random.random() if rnum>self.searchChoice(len(self.ao.blackboard), self.ao.totalRobots()): self.__task = "Search" #print "going to search" else: self.__task = "Forage" #print "going to forage" #now, if it is assigned a forage task, pick a pile from the blackboard if self.__task=="Forage": #example of what a blackboard element may look like: #{"coordinates":..., "pheromones":..., "treshold": (k in the articles)} #function from articles rnum = random.random() denominator = sum([((pile["pheromones"]+self.treshold(len(self.ao.blackboard)))**self.ao.l) * self.distance2(Distance(self.coordinates,pile["coordinates"])) for pile in self.ao.blackboard]) treshold = 0#this is a different treshold. Sorry for using the same word twice for pile in self.ao.blackboard: treshold += ((pile["pheromones"]+self.treshold(len(self.ao.blackboard)))**self.ao.l)*self.distance2(Distance(self.coordinates,pile["coordinates"])) if rnum <treshold/denominator: self.__goal=pile["coordinates"] break #this is the pile it gets assigned too #at this point it is clear what the robot should do movements=self.ao.getMovements(self.coordinates)#looks like (where I can go, where the piles are) #if extremeDebug: print "movements is "+ str(movements) if debug: if len(movements[0])<=1: print "no movements possible except for staying" if len(movements[0])<=len(movements[1])+1: print "only pile moves or staying" if not movements[0]: print "no movements" if self.__task == "Forage": if not self.ao.getPileSizeAt(self.__goal): self.__task="Search" #the pile was removed before this robot arrived #self.direction=None #set random direction newdirection = self.chooseRandomDirection(movements[0]) self.direction = (newdirection[0]-self.coordinates[0], newdirection[1]-self.coordinates[1]) self.setForage()#chance of going to forage for another pile #hence start searching for another pile elif self.__goal in movements[0]: self.__previousCoordinates=self.coordinates self.coordinates=self.__goal self.direction = (self.__previousCoordinates[0]-self.coordinates[0], self.__previousCoordinates[1]-self.coordinates[1]) #mirrored direction blackboardElement=[bbelem for bbelem in self.ao.blackboard if bbelem["coordinates"]==self.__goal][0] #n.b. we assume that piles don't overlap #if not self.ao.getPileSizeAt(self.__goal): #print "no pile at goal "+str(self.__goal) #print "but do have blackboard element "+ str(blackboardElement) blackboardElement["pheromones"]=self.__dropPile( blackboardElement["pheromones"], self.ao.getPileSizeAt(self.__goal), self.ao.getVictimsAt(self.__goal)) #drop pheromones ###### hier gaat het fout als de robot op pad is naar een pile die niet meer bestaat elif movements[1] and self.ao.goalSwitch==2: #pick a pile point and just go for it relevantBlackboard = [bbelem for bbelem in self.ao.blackboard if bbelem["coordinates"] in movements[1]] if relevantBlackboard: bbchoice = random.choice(relevantBlackboard) self.__previousCoordinates = self.coordinates self.coordinates = bbchoice["coordinates"] self.direction = (self.__previousCoordinates[0]-self.coordinates[0], self.__previousCoordinates[1]-self.coordinates[1]) #mirrored direction bbchoice["pheromones"] = self.__dropPile( bbchoice["pheromones"], self.ao.getPileSizeAt(self.coordinates), self.ao.getVictimsAt(self.coordinates)) else: coordchoice = random.choice(movements[1]) self.ao.blackboard.append( {"coordinates":coordchoice, "pheromones": self.__dropPile( 0, self.ao.getPileSizeAt(coordchoice), self.ao.getVictimsAt(coordchoice))})#treshold will be changed anyways self.__previouscoordinates = self.coordinates self.coordinates = coordchoice self.direction = (self.__previousCoordinates[0]-self.coordinates[0], self.__previousCoordinates[1]-self.coordinates[1]) #mirrored direction else: if self.ao.goalSwitch == 1: movements[0] = [movement for movement in movements[0] if not movement in movements[1]]#explicitly don't want to get into a wrong pile if self.ao.goalSwitch == 1 preferedDirection = self.pickDirection(self.__goal, self.coordinates) preferedCoordinate = self.pickCoordinates(preferedDirection, movements[0]) if preferedCoordinate:#if it's not None self.__previousCoordinates=self.coordinates self.coordinates = preferedCoordinate #since we can go there and that's where we want to go self.direction = (self.coordinates[0]-self.__previousCoordinates[0], self.coordinates[1]-self.__previousCoordinates[1]) else: #traveling in a straight line to the target is not possible :( #try riding in the preset direction try: #this goes wrong if self.direction=(0,0) preferedCoordinate = self.pickCoordinates( self.pickDirection( (self.coordinates[0]+self.direction[0], self.coordinates[1]+self.direction[1]), self.coordinates), movements[0]) if preferedCoordinate: self.__previousCoordinates=self.coordinates self.coordinates = preferedCoordinate #self.direction stays the same #else choose a left or right at random else: rot = random.choice((-1,1)) preferedCoordinate = self.pickCoordinates( self.pickDirection( self.__goal, self.coordinates), movements[2]) #Where we would have wanted to go if not preferedCoordinate: print "no prefered coordinate found" print self.__goal print self.pickDirection(self.__goal,self.coordinates) attempts=1 chosen=False while attempts<3 and not chosen: rotlist = [point for point in movements[0] if (point[0]*preferedCoordinate[1] -\ point[1]*preferedCoordinate[0])*rot>0\ and point!=self.coordinates]# points with the correct rotation direction if len(rotlist)>0: #we want the one closest to the prefered coordinates #TODO prevent loop movements #meh (see other comment about it) chosenCoordinate = min(rotlist, key=lambda point: Distance( point, preferedCoordinate)) chosen =True else: rot = -rot attempts+=1 if not chosen: #can this occur? raise Exception #I have no inspiration right now if not chosenCoordinate in movements[0]: print "blaaaa :S" self.__previousCoordinates = self.coordinates self.coordinates=chosenCoordinate self.direction = (self.coordinates[0]-self.__previousCoordinates[0],self.coordinates[1]-self.__previousCoordinates[1]) except TypeError: #no preset direction rot = random.choice((-1,1)) preferedCoordinate = self.pickCoordinates( self.pickDirection( self.__goal, self.coordinates), movements[2]) #Where we would have wanted to go attempts=1 chosen=False while attempts<3 and not chosen: rotlist = [point for point in movements[0] if ((point[0]-self.coordinates[0])*(preferedCoordinate[1]-self.coordinates[1]) -\ (point[1]-self.coordinates[1])*(preferedCoordinate[0]-self.coordinates[0]))*rot>0\ and point!=self.coordinates]#points with the correct rotation direction if len(rotlist)>0: #we want the one closest to the prefered coordinates #TODO prevent loop movements #meh (see other comment about it) chosenCoordinate = min(rotlist, key=lambda point: Distance(point,preferedCoordinate)) chosen =True else: rot = -rot attempts+=1 if not chosen: #can this occur? raise Exception #I have no inspiratino right now if not chosenCoordinate in movements[0]: print "I'm going yellow" self.__previousCoordinates = self.coordinates self.coordinates=chosenCoordinate self.direction = (self.coordinates[0]-self.__previousCoordinates[0],self.coordinates[1]-self.__previousCoordinates[1]) elif self.__task == "Return": #due to the randomnes in the algorithm for foraging, we need to do some extra work to keep the group together #the idea is as follows: #whenever a choice needs to be made (based on randomnes), the first robot to "think" makes the choice #this robots than puts a local message out, so that all the robots within a small radius, say self.speed, make the same decision #to prevent miscommunication, all local messages are deleted after the execution of update() #if a local message is recieved, attempt to obey it #else try to go to the CZ #if that's not possible, choose a direction and send that direction as a local message if self.__localMessage: direction = self.pickDirection(self.__localMessage, self.coordinates) #take the coordinate closest to direction if self.coordinates not in movements[1]: preferedCoordinate = min( [coord for coord in movements[0] if coord not in movements[1]] ,key=lambda x:Distance(x,direction) )#it is important now to not get into another pile else: preferedCoordinate = min(movements[0], key=lambda x: Distance(x,direction)) #this might go verry badly #nope self.__previousCoordinates = self.coordinates self.coordinates = preferedCoordinate self.direction = (self.coordinates[0]-self.__previousCoordinates[0],self.coordinates[1]-self.__previousCoordinates[1]) else: preferedDirection = self.pickDirection(self.__goal, self.coordinates) preferedCoordinate = self.pickCoordinates(preferedDirection, movements[0]) if preferedCoordinate and not preferedCoordinate in movements[1]:#it is important now that we don't accidentaly go into another pile self.__previousCoordinates = self.coordinates self.coordinates = preferedCoordinate self.direction = (self.coordinates[0]-self.__previousCoordinates[0],self.coordinates[1]-self.__previousCoordinates[1]) else: # a choice needs to be made rot = random.choice((-1,1)) preferedCoordinate = self.pickCoordinates( self.pickDirection(self.__goal,self.coordinates), movements[2]) #Where we would have wanted to go if not preferedCoordinate: print "no prefered coordinate in return" print self.pickDirection(self.__goal,self.coordinates) print self.__goal attempts=1 chosen=False while attempts<3 and not chosen: rotlist = [ point for point in movements[0] if ((point[0]-self.coordinates[0])*(preferedCoordinate[1]-self.coordinates[1]) -\ (point[1]-self.coordinates[1])*(preferedCoordinate[0]-self.coordinates[0]))*rot>0\ and point!=self.coordinates]# points with the correct rotation direction if len(rotlist)>0: #we want the one closest to the prefered coordinates #TODO prevent loop movements #meh, doesn't seem to be necessary (would only occur in very nasty situations chosenCoordinate = min(rotlist, key=lambda point: Distance(point,preferedCoordinate)) chosen =True else: rot = -rot attempts+=1 if not chosen: #can this occur? raise Exception #I have no inspiratino right now self.ao.sendLocalMessage(self.coordinates, self.speed, chosenCoordinate, self.__lastID) #finetuning: radius might need to be finetuned # meh self.__previousCoordinates = self.coordinates self.coordinates=chosenCoordinate self.direction = (self.coordinates[0]-self.__previousCoordinates[0],self.coordinates[1]-self.__previousCoordinates[1]) elif self.__task == "Search": if not self.direction or self.direction==(0,0): newdirection = self.chooseRandomDirection(movements[0]) self.direction = (newdirection[0]-self.coordinates[0], newdirection[1]-self.coordinates[1]) if extremeDebug: print "had no direction, so chose "+str(self.direction) #except IndexError: # self.direction = self.chooseRandomDirection(movements[2]) #wait... this shouldn't be possible #try to go in self.direction #if that isn't possible, choose a different direction #whenever a pile is encountred, add it to the blackboard and go to the pile if movements[1]: #there is a pile that can be reached #we assume the robots can see the size of a pile #we assume that the robot can see what pile what point belongs to if extremeDebug: print "could reach piles at "+str(len(movements[1]))+" coordinates" pilesInReach = self.ao.pilesAt(movements[1]) #we want to add only those piles that aren't already in the blackboard newPiles = [pile for pile in pilesInReach if pile not in self.ao.pilesAt([p["coordinates"] for p in self.ao.blackboard])] #this is ugly and inefficient if newPiles:#non empty newcoord=[] for pile in newPiles: nc = random.choice([coord for coord in movements[1] if pile.isAt((coord,))]) self.ao.blackboard.append({ "coordinates":nc, "pheromones":self.__dropPile(0,pile.pileSize(),pile.pileVictims()) }) newcoord.append(nc) if not self.ao.getPileSizeAt(nc): print "wrong bbelem added" raise Exception #USE #just pick a coordinate in view for the pile and add {coordinate, pheromones} to the blackboard #now that all new piles are added to the blackboard, let's go to one of them chosenCoordinate = random.choice(newcoord) self.__previousCoordinates = self.coordinates self.coordinates=chosenCoordinate self.direction = (self.__previousCoordinates[0]-self.coordinates[0], self.__previousCoordinates[1]-self.coordinates[1]) #mirrored direction else: #no new piles #see if any of the coordinates are already on the blackboard blackboardOptions = [bbelem for bbelem in self.ao.blackboard if bbelem["coordinates"] in movements[1]] if blackboardOptions:#nonempty choice = random.choice(blackboardOptions) choice["pheromones"] = self.__dropPile( choice["pheromones"], self.ao.getPileSizeAt(choice["coordinates"]), self.ao.getVictimsAt(choice["coordinates"])) self.__previousCoordinates = self.coordinates self.coordinates = choice["coordinates"] self.direction = (self.__previousCoordinates[0]-self.coordinates[0], self.__previousCoordinates[1]-self.coordinates[1]) #mirrored direction else: #so no of the pile points we can reach are on the blackboard. W #there are two main options for action: #the first is to choose one of the piles and head for the point in the pile that is in the blackboard #the downside is that that might be verry inefficient #the other is to add a new point to the blackboard #the downside to that is that the same pile will now be in the blackboard more than once #we'll take the second approach since it kinda makes more sence in the case of large piles #we'll do this to only one of the piles though, to prevent enormous growth of the blackboard pileChoice = random.choice(pilesInReach) reachable = [coord for coord in movements[1] if pileChoice.isAt((coord,))] nc = random.choice(reachable) self.ao.blackboard.append({ "coordinates":nc, "pheromones":self.__dropPile(0,pileChoice.pileSize(),pileChoice.pileVictims()) }) if not self.ao.getPileSizeAt(nc): print "wrong bbelem added" raise Exception self.__previousCoordinates = self.coordinates self.coordinates = nc self.direction = (self.__previousCoordinates[0]-self.coordinates[0], self.__previousCoordinates[1]-self.coordinates[1]) #mirrored direction else: #no piles can be reached in one step, so try continuing in a straight line. If this fails, pick a random direction that can be moved in. preferedCoordinate = self.pickCoordinates( self.pickDirection( (self.coordinates[0]+self.direction[0], self.coordinates[1]+self.direction[1]), self.coordinates), movements[0] ) if extremeDebug: print "pref coord 1 "+str(preferedCoordinate) print "with direction "+ str(self.direction)\ +" and coordinates "+str(self.coordinates) if preferedCoordinate: self.__previousCoordinates = self.coordinates self.coordinates = preferedCoordinate self.direction = (self.coordinates[0]-self.__previousCoordinates[0],self.coordinates[1]-self.__previousCoordinates[1]) if extremeDebug: print "went to that" else: if extremeDebug: print "so didn't go for that" self.__previousCoordinates = self.coordinates self.coordinates = random.choice( [coord for coord in movements[0] if Distance(self.coordinates, coord)>= self.speed-2 ])#pick a random direction we can go in self.direction = self.direction = (self.coordinates[0]-self.__previousCoordinates[0],self.coordinates[1]-self.__previousCoordinates[1]) if extremeDebug: print "but went for "+str(self.coordinates)\ +" wo I now have direction "+ str(self.direction) if self.coordinates not in movements[0]: print "went yellow on search" #for debugging: #newmovements= self.ao.getMovements(self.coordinates) #if extremeDebug: print "now the new movements are "+ str(newmovements) #if not newmovements[0]: # print "magic happned at search" self.__localMessage = None #clear the local message #print "new coordinates are "+ str(self.coordinates) def runSimulation(size=(500, 500), cz=(0,0), nRobots=100, piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],30000), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3)], obstacles=[((100,100),(200,200)), ((30,100),(40,200)),((300,300),(340, 320))], evaporatePile = lambda x:.90*x, dropPile = lambda x,y,z:x+.05*y*(z/10.+.1), treshold = lambda x: min(1,10-x), goalSwitch = 0, distance1=lambda x:1, distance2=lambda x:1, searchChoice = lambda bblen, nrob: min((10.*bblen)/(2*nrob),1), l=2, speed=6, waitingtime = 100): done = False #it = 0 simulation = AO(size=size, cz=cz, nRobots=nRobots, piles=piles, obstacles=obstacles, evaporatePile=evaporatePile, dropPile=dropPile, treshold=treshold, l=l, speed=speed, distance1=distance1, distance2=distance2, goalSwitch = goalSwitch) while not done: try : if not simulation.update(): done = True except IndexError: return simulation #if not graphics: # it +=1 # print it #pygame.time.wait(waitingtime) #pygame.quit() return simulation if __name__=="__main__": import settings import os def runner(num=1): researchData=[] for i in range(num): simulation = runSimulation( size = settings.size, cz = settings.cz, nRobots = settings.nRobots, piles = settings.piles, obstacles = settings.obstacles, evaporatePile = settings.evaporatePile, dropPile = settings.dropPile, treshold = settings.treshold, l = settings.l, distance1 = settings.distance1, distance2 = settings.distance2, speed = settings.speed, goalSwitch = settings.goalSwitch) #run the simulation to obtain researchData researchData.append(simulation.researchData)# the stuff we're interested in #output everything to the file location try: f=open("./results/"+settings.name+str(len(os.listdir("./results")))+".py", "w") f.write("data = "+repr(researchData)) f.close() return True except IOError: return False #pool = multiprocessing.Pool(10) #pool.map(runner, ["output"+str(i)+".py" for i in range(10)]) runner()

## Parameters and USE

To incorporate ethical decision making in the design of our algorithms and simulation, we have 8 parameters for decision making. In this section we will give an overview of these parameters. We have also run the simulation with different values for the parameters based on underlying ethical choices. We will elaborate on these choices and review the results.

The parameters for decision making are the following:

- evaporatePile, a function that decides the speed of evaporation of pheromones. Fast evaporation equalizes priorities fast while slow evaporation will fix priorities.
- Input: pheromone level at the end of time step t
- Output: pheromone level at the beginning of time step t+1

- dropPile, Amount of pheromones dropped by a robot. Dropping large amounts of pheromones will increase the relevance of the pile more than dropping small amounts. An ethical choice to be made here is how the relevance of a pile is determined by the number of victims trapped at it, and by the difficulty of freeing them.
- Input: current pheromone level, pile size (amount of robots needed to clear the pile entirely), number of victims trapped at the pile
- Output: updated pheromone level

- threshold, a function of the blackboard size which plays the role of k in Media:Liu,_Chen,_Wang_-_2013_-_A_Model_of_Rescue_Task_in_Swarm_Robots_System.pdf. A high treshold will give piles with little pheromones a relatively larger chance of being chosen when a robot goes foraging
- Input: number of blackboard elements
- Output: threshold

- l, the sensitivity of the choice process to differences in pheromones. Large l will make piles with large of amounts of pheromones much more likely to be chosen
- This is a constant

- distance1, a function of the distance between the robot and a pile that influences the chance of the robot choosing that pile as its goal if the robot goes foraging from a position other than the CZ. This can be used to make robots prefer nearby piles over piles that are far away.
- Input: the distance between the robot and a pile
- Output: a factor in the probability of this pile being chosen

- distance2, a function of the distance between the CZ and a pile that influences the chance of a robot choosing that pile as its goal if the robot goes foraging from the CZ. This can be used to give higher priorities to piles that are nearby the CZ (and thus prioritizing easier rescue).
- Input: the distance between the CZ and a pile
- Output: a factor in the probability of this pile being chosen

- goalSwitch, a parameter deciding whether or not a robot may ignore its original goal in order to go to a pile it can immediately reach. This corresponds to the ethical dilemma of whether, if a robot is set out to save person a, it may ignore person b who can be saved by it immediately.
- 0: don't consciously change goals, but if the robot happens to get into another pile, it will start helping out there.
- 1: avoid other piles than the goal, so don't help out at piles that aren't the original goal.
- 2: if another pile is reachable in one time step, go for that pile, no matter what the original goal was.

- searchChoice, a function determining chance of going to foraging mode or going to search mode. This reflects the choice of how important finding unknown victims is compared to saving known victims
- Input: size of blackboard, number of available robots
- Output: the probability of a robot going foraging (n.b. 1-this value is the probability of a robot going searching)

As mentioned, varying these parameters based on both ethical decisions and research interests as to their influence, we've created different settings for running the simulation. We will now discuss these settings and the accompanying results. Many graphs we have created but haven't put into this wiki can be found in media:results1.zip and media:results2.zip.

### Influence of dropPile and evaporatePile when ignoring presence of victims

The first experiment we will describe here is to the influence of the drop size and evaporation speed when ignoring the presence of victims. The first settings where

name = "dropNoHumans1" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 1 distance2 = lambda x: 1 goalSwitch = 0 searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

We don't take distance into account and our searchChoice comes down to saying that if we have less than 10 robots per blackboard element, we want to go foraging for sure since we then can't miss the robots to searching, and otherwise the chance of going foraging should be linear in the number of blackboard elements.

These settings resulted in the following progress of the total size of the piles for 20 simulations

with which comes down to the following average progress

For the second settings we used a larger drop

name = "dropNoHumans2" dropPile = lambda x,y,z:x+.07*y

which resulted in

and with averaging

For the third a smaller drop

name = "dropNoHumans3" dropPile = lambda x,y,z:x+.03*y

which resulted in

and with averaging

for the fourth settings, the difference with the first settings was in the evaporation speed

name = "evaporateNohumans1" evaporatePile = lambda x:.80*x

which resulted in

and with averaging

for the fifth settings, the difference with the first settings was again in the evaporation speed

name = "evaporateNohumans2" evaporatePile = lambda x:.95*x

which resulted in

and with averaging

Now, to give an overview of the differences, the mean progress for the different settings is shown by

and the duration of the simulations (hence the duration before all piles are cleared) is shown by

This indicates that some settings might be better than others (e.g. settings 1 might be better than settings 3) but we have to little data to draw hard conclusions. It seems that out of these possibilities, the first settings might be the best, but more simulations might be necessary to investigate this further.

### Influence of dropPile and evaporatePile when taking victims into account

In the second experiment we do the same, but do take the number of victims into account, as can be seen from our choice of dropPile. For our first settings we took

name = "dropHumans1" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y*(.2*z + .2) #normal (1) if z == 4 treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 1 distance2 = lambda x: 1 goalSwitch = 0 searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

Now the number of victims at the pile is taken into account. We take it as [math]\displaystyle{ .2\cdot \text{number of victims} + .2 }[/math]

The [math]\displaystyle{ +.2 }[/math] is necessary to ensure that piles without victims are still cleared (efficiently). We choose this approach because it is somewhat utilitarian in the sense that every human life is worth as much, it being somewhat linear in the number of victims. We will look at sub linear growth later. For compactness we will not show all the graphs for all the settings, but only show the combined results.

For the second settings:

name = "dropHumans2" dropPile = lambda x,y,z:x+.07*y*(.2*z + .2) #normal (1) if z == 4

For the third:

name = "dropHumans3" dropPile = lambda x,y,z:x+.03*y*(.2*z + .2) #normal (1) if z == 4

For the fourth:

name = "evaporateHumans1" evaporatePile = lambda x:.80*x

For the fifth:

name = "evaporateHumans2" evaporatePile = lambda x:.95*x

All using the first settings as a base.

The mean progress is shown by

and the duration is shown by

In this case the results are even closer and although settings3 seems to give somewhat better results than the other settings, this might be purely by chance. One thing that does strike the eye is that all of these settings seem to perform better than most of the settings in the previous experiment where humans wheren't taken into account. Note that we're note measuring when all humans are rescued (although that usually coincides with the duration of the simulation for this particular map), so it might be just a quirk of this particular choice of where the piles are. It would be interesting however to look more into this by using larger data sets, taking different maps into account.

### Influence of distance functions

For the third experiment we will look into the influence of the distance functions. We will do this from the perspective of ethical decision making, taking stance that we shouldn't ignore humans near us that need help. We will also investigate the influence of taking the same distance functions but without taking the number of victims at a pile into account, and the influence of choosing to search more - from the perspective that known victims should be helped first. The first settings file looks as follows:

name = "ClosestFirst1" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y*(.2*z + .2) #normal (1) if z == 4 treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 2.*speed/(1+x) #normal for x==speed distance2 = lambda x: 1 goalSwitch = 2 searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

Note that we've put the goalSwitch to 2, so that if a robot comes across a pile it will always go for it. Now distance2 is still constant, so that distance doesn't play a role when starting at the CZ, but distance1 decreases for increasing distance, so that if a robot goes from searching to foraging, or switches goals during foraging due to its original goal being cleared, the robot gives more priority to piles nearby. We'll now show the rest of the settings files, which are basically explained above.

name = "ClosestFirst2" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y*(.2*z + .2) #normal (1) if z == 4 treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 2.*speed/(1+x) #normal for x==speed distance2 = lambda x: 11.*speed/(1+x) #normal for x==10*speed goalSwitch = 2 searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

The next two will not take the number of victims at a pile into account

name = "ClosestFirst3" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 2.*speed/(1+x) #normal for x==speed distance2 = lambda x: 1 goalSwitch = 2 searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

name = "ClosestFirst4" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 2.*speed/(1+x) #normal for x==speed distance2 = lambda x: 11.*speed/(1+x) #normal for x==10*speed goalSwitch = 2 searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

The next two make it less likely for a robot to go searching, so opting for rescuing known victims instead of looking for unknown victims faster

name = "ClosestFirst5" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y*(.2*z + .2) #normal (1) if z == 4 treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 2.*speed/(1+x) #normal for x==speed distance2 = lambda x: 1 goalSwitch = 2 searchChoice = lambda bblen, nrob: min((20.*bblen)/(nrob),1)

name = "ClosestFirst6" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y*(.2*z + .2) #normal (1) if z == 4 treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 2.*speed/(1+x) #normal for x==speed distance2 = lambda x: 11.*speed/(1+x) #normal for x==10*speed goalSwitch = 2 searchChoice = lambda bblen, nrob: min((20.*bblen)/(nrob),1)

The mean progress is shown in

and the duration for the different settings is shown in

Which shows that going for the closest pile, especially when already in the field, yield much better results than in the previous two experiments. Taking distance into account when starting from the CZ seems however slightly worse than not doing so, although it might be so that this parameter needs some optimisation.

### Dedication

Another stance one might take is that when you have committed to saving a certain person, you should stick to that goal, because that person is depending on you. In this experiment, this point of view is explored. The first settings are given by

name = "Dedication1" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y*(.2*z + .2) #normal (1) if z == 4 treshold = lambda x: max(1,5-x) l=2 speed=6 distance1 = lambda x: 1 distance2 = lambda x: 1 goalSwitch = 1 searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

where the goalSwitch is set to 1, meaning that even when a robot could go to another pile in just one step, it will keep going for its original goal. In the following settings we will experiment with the influence of the searchChoice, since for sticking to a goal to be justified, the goal must be set well informed, and also from the point of view that searching may be a task worth sticking to itself. We also again looked at the influence of taking the number of victims into account. Furthermore, to look into the reliability of an n=20 experiment, we ran another 20 simulations with the same settings as the first settings. We'll now list the divergence in settings from settings1:

name = "Dedication2" searchChoice = lambda bblen, nrob: min((20.*bblen)/(nrob),1)

making searching less likely

name = "Dedication3" searchChoice = lambda bblen, nrob: min((5.*bblen)/(nrob),1)

making searching more likely

name = "Dedication4" dropPile = lambda x,y,z:x+.05*y searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

not taking victims into account

name = "Dedication5"

The last settings are the same as the first.

The mean progress is shown by

and the duration of the simulations by

Which shows that the role of chance is still very large for such a small experiment.

### Kant

In the last experiment, we look at what happens if one takes the stance that two humans aren't worth twice as much as one. Furthermore, we look into the influence of the threshold. Having a large threshold means that piles with little pheromones remain relatively likely to be picked by a robot. The first settings are given by

name = "Kant1" size=(500, 500) cz=(0,0) nRobots=100 piles=[((100,200), (130,240), [1,1,6,3,1,10, 20, 11, 30],0), ((350,71), (400,120), [30,1,20,3,31,16, 12, 22],5), ((0,300),(100, 360),[21,24,33,2,32,33,34,35],3), ((390,380),(420,450),[1,1,2,4,2,30,2,20,13,10,20],1)] obstacles=[((100,100),(200,200)), ((330,100),(340,200))] evaporatePile = lambda x:.90*x dropPile = lambda x,y,z:x+.05*y*(.2*z**.5 + .2) #grows sublinear treshold = lambda x: 5 l=2 speed=6 distance1 = lambda x: 1 distance2 = lambda x: 1 goalSwitch = 0 searchChoice = lambda bblen, nrob: min((10.*bblen)/(nrob),1)

where the square root is chosen for its sub linear growth. Comparing this to the usual growth in the second settings

name = "Kant2" dropPile = lambda x,y,z:x+.05*y*(.2*z + .2)

and repeating for different thresholds

name = "Kant3" treshold = lambda x: 10

name = "Kant4" dropPile = lambda x,y,z:x+.05*y*(.2*z + .2) treshold = lambda x: 10

name = "Kant5" dropPile = lambda x,y,z:x+.05*y*(.2*z + .2) treshold = lambda x: 1

The results are the following:

Showing no significant differences. More data is needed to draw conclusions from this experiment.

## Conclusions and Recommendations

The above mainly shows two things:

- taking distance into account makes your rescue operation more efficient
- more data is needed to really investigate the influence of the other parameters

An important recommendation for this specific approach is fixing the flow for the Returning. Change it into

- Returning
- If a local message is received it tries to follow up on that message. If no message is received:
- The robot tries to go in a straight line towards the Clear Zone
- If that's not possible try continuing in the previous direction
- Whenever that's not possible choose left or right and go into that direction (deviating from the straight line towards the goal as little as possible)
- Also send a local message to all near robots that are returning to the CZ to go into that direction

the python code that would implement this would be very similar to the code in Foraging that does the same thing.

A more thorough revamp of the behaviour of the robots, which is highly recommended, would be to construct a graph representation of the world on the go, so that short paths can be remembered, and another (possibly ant colony based) swarm algorithm could than be used to find the actual shortest paths (within that graph).

Back to: PRE2015_2_Groep1