Cooperative Fire Fighters

(1)

Cooperative Fire Fighters

Uy Quoc Ton Tran

Master’s Thesis, Autumn 2017

(2)

(3)

Cooperative Fire Fighters

Uy Quoc Ton Tran

i

(4)

(5)

preface

This thesis concludes my master’s degree in Informatics: Programming and Networks at the University of Oslo.

I would like to thank my supervisor Tapia Tarifa, Lizeth for her precious time and her patience with me. I also would like to thank my parents and sister for supporting me and always expressing how proud they are of me.

Finally, all of my friends at the department is what made my stay at the department worth it. I would not have made it this far without their support and I will miss seeing them every day

University of Oslo, July 2017 Uy Quoc Ton Tran

iii

(6)

(7)

abstract

Artificial intelligence is one of the hottest topics in this decade, with cars driving by themselves and robot vacuum cleaners cleaning the floors for us we face a challenge to control these automated concepts in an efficient way.

Swarm intelligence is a concept employed in work on artificial intelligence and focuses on getting these robots to cooperate with one another to achieve a common goal. By utilizingswarm intelligence when developing protocols, we gain much more efficient systems with less resources spent. In this thesis we will concern a problem called the Fire Fighter problem where we introduce fire extinguishing robots that cooperates to extinguish forest fires. We will define a protocol to our Fire Fighter problem and present a prototype simulation tool that has been developed.

v

(8)

(9)

List of Figures

1.1 Cooperativeness with two agents with SWEEP [1] . . . 3

2.1 Processing figures explanation . . . 11

2.2 Illustration of borders . . . 13

2.3 8-neighbor illustration . . . 14

2.5 Fire spread illustration . . . 19

3.1 SWEEP protocol from Yaniv et al. [2] . . . 22

3.2 Critical vertex example . . . 32

3.3 Junction example . . . 35

3.4 Junction solution . . . 37

3.5 Junction solution . . . 38

3.6 Clockwise ring list . . . 40

3.7 Agent clockwise movement . . . 41

3.8 Example of flame connectivity violation . . . 43

3.9 Example of preserving flame connectivity . . . 44

5.2 Fire spread from a one dimensional view . . . 52

5.3 Fire isolation from a one dimensional view . . . 52

5.4 Complete fire isolation . . . 53

5.5 Cooperativeness with two agents . . . 54

5.6 Extinguishing of a ring with SWEEP [1] . . . 57

5.7 Agent initial movement with SWEEP [1] . . . 58

6.1 Encapsulating with different starting vertices . . . 62

x

(13)

List of Tables

2.1 Example of an instruction stack . . . 12 3.1 Instruction stack for figure 3.8 . . . 43 3.2 Instruction stack for figure 3.9 . . . 44

xi

(14)

Listings

2.1 Agent basic memory attributes . . . 16

2.2 Algorithm for spreading fire . . . 18

2.3 Critical vertex mathematical representation . . . 20

3.1 Java code example . . . 25

3.2 Java method signature . . . 26

3.3 Data structure for Vertex and State . . . 28

3.4 Data structure for Vertex and State [3] . . . 29

3.5 Forest initialization [3] . . . 30

3.6 Burn methods and helping methods [3] . . . 31

3.7 Handling junctions i Java [3] . . . 36

4.1 Number operations example with JML [3] . . . 47

4.2 JML invariants for Vertex [3] . . . 48

4.3 JML invariants for Forest [3] . . . 49

4.4 JML invariants for Agent [3] . . . 50

5.1 How Tapia Tarifa checks for critical vertices for CLEAN in ABS [4] . . . 56

xii

(15)

Chapter 1 Introduction

1.1 Motivation

In an ever changing world where everyone has a independent computer in their pockets and where we are getting more focused on Internet of Things (IoT) it is getting more and more important to make all the devices cooperate with each other effortlessly [5]. Our problem, called the Fire Fightersproblem, focuses on this very concept by utilizing robots to work together to extinguish a forest fire. Just like the concept of IoT, we will be creating a concept that will be largely beneficial for us humans. Making machines and robots do our work does not only make communities spend less resources doing automated jobs, but also accomplishes the tasks much faster. These benefits are important when designing a system that replaces human resources, but our problem considers a job that would otherwise put humans at big health risks and might even save peoples lives.

1.1.1 Swarm Intelligence

With robotics becoming more useful and evolving faster than ever, we find that one robot cannot always do big jobs efficiently. Especially if the amount of work is increased by time, then the problem might even become impossible. Which is why we are in need of multiple robots cooperating to achieve completion of a task. We see this challenge appearing in front of us in nature every day [6]. Either with ants fetching food for ant-larvae or bees producing honey for the bee larvae. Obviously it wouldn’t have been possible to feed their whole population with just one ant or bee to fetch food.

Swarm intelligence concerns systems that consists of agents that are de- 1

(16)

2 1. Introduction centralized meaning that there are no centralized controller or boss that instructs and commands the agents. The agents are completely independent from one another as well meaning that if the majority of the agents would become damaged and unable to work, it would not stop the remaining agents to work and solve the problem if possible [7]. By utilizing this concept that we learned from swarms in nature we are able to construct protocols that simulates the same behaviour with robots.

1.1.2 Real World Applications

During this thesis we have to keep in mind that theFire Fightingproblem is just one example of a real world application. Other real world applications can be used as examples for the hybrid environment such as an epidemic or various search engine techniques. Not only does the hybrid environment fit theFire Fightersproblem but the simulation will be more realistic towards a real world fire extinguisher problem, which will be described later in this thesis. These applications will be further discussed and explained in chapter 2.

1.2 Related Work

This thesis will mostly be reusing content from other works to spare us from a great deal of works so that we may focus on our core ideas and concepts.

Two important projects here are Solid Waste Environmental Excellence Protocol (SWEEP) and Group of Unmanned Assistant Robots Deployed In Aggregative Navigation by Scent (GUARDIANS) that both concerns fire fighting problems but with totally different contexts and goals. Another protocol,CLEANwhich largely related toSWEEP, will also be discussed as well as as Stochastic Diffusion Search (SDS).

1.2.1 SWEEP

Our protocol that we will introduce in this thesis will largely be based on the SWEEP that is presented by Yaniv et al. [7]. Yaniv’s et al. content will not only help us save time by reusing many of their key features with terminology we use throughout this thesis, but also with the development of our own protocol.

The basic concept of SWEEP concerns a dirty floor that is a single connected grid and robot cleaners that cleans the dirty floor. The entire floor is also a grid that consists of a binary value that represents the vertex’s

(17)

1.2. Related Work 3 contamination which is represented as eitheronoroff. Therefore all vertices that have their contamination value as on is the dirty floor. The dirty floor has a property of spreading over time so the robot cleaners needs to be efficient at cleaning the floor since the floor might spread itself to a point where the work becomes too much for the cleaners to handle. The pattern at which the cleaners move becomes a crucial factor. By having the cleaners move and clean in a "peeling" manner the dirty floor will get more limited to spreading and therefore it is an efficient way of cleaning the dirty floor. This peeling action is shown in figure 1.1 that illustrates two agents cooperating to clean a dirty floor. Because the two agents are not moving in the exact same pattern, they have some sort of a priority system involved which ensures that the agents are unique but also ensures their uniqueness in their movement.

Figure 1.1: Cooperativeness with two agents with SWEEP [1]

1.2.2 CLEAN

Tapia Tarifa’s thesis concerns the CLEAN protocol which, similar to SWEEP, also concerns cooperative cleaning agents cleaning a dirty [4]. She makes an implementation of the protocol with ABS which is an actor-based, object-oriented, executable modeling language [8]. The main difference however is that CLEAN solves dirty floors that cannot spread meaning that the environment is static. This is means any given dirty floor pattern is solvable as long as there are at least one cleaning agent cleaning the floor.

Because of this, the protocol does not need to consider complex problems that will make the problem impossible. This will be taken into account when we explain the complexities of the Fire Fighting problem.

(18)

4 1. Introduction

1.2.3 GUARDIANS

Very much like SWEEP, GUARDIANS concerns a swarm that works together to solve a common goal in an unknown area. Common features between these different problems focuses on agents with a finite memory that is only given a starting location and traverse a map. Where these two protocols differs is their goal, which in the GUARDIANS project is to map an unknown area that may be too dangerous for humans to traverse so that the human may know if it is safe for them or not [9]. The robot is equipped with different sensors like temperature sensors that can determine the level of temperature that is dangerous for humans as well as gas and smoke sensors that takes into account for other health factors for humans.

The purpose of a GUARDIANS robot is also to accompany a human in dangerous areas and guide us through zones that are safe and warn us about areas that is not suited for us.

1.2.4 SDS

SDS is a much more abstract swarm intelligence concept than the previously mentioned protocols and revolves around agents working together to gather information to reach a conclusion [10]. Communication is a key factor and Mohammad introduces a sobering example to present the benefits of communication with the story of blind men and the elephant by Saxe J. G. [11]. The story focuses on six blind men approaching an elephant from different angles and gathering different pieces of information such as a man approaching from the side and thinking that he hit a wall and a man approaching the elephants tusk and thinking that he approached a spear and so on. The moral of the story from a swarm intelligence perspective is that if agents, being the blind men in the story, were to work together and share information through communication, they would have much to gain when it comes to having a clear picture of the real world. This is also the very key goal that SDS tries to achieve through its architectures.

By utilizing this concept for search engines, we are able to efficiently fetch data with multiple agents and reassemble the data and conclude with an accurate result.

1.3 The Little Twist

Just like GUARDIANS and SWEEP our own protocol also concerns a grid or map that is unknown to the swarm that consists of agents with finite memory given only a starting point to the swarm. Our problem focuses on

(19)

1.4. Research Questions 5 agents being fire extinguishing robots in an unknown burning forest. The burning area is a single connected graph that will maintain connected by the protocol because it also relies on the given graph being connected for the agents to extinguish the whole burning area. Just like SWEEP and CLEANthe vertices in our protocol represents an area of our environment being a forest in our case. Instead of each vertex’s contamination value as a binary value of on and off, we now introduce two states as their values, burning ason and standing as off. Our protocol also considers a damaged areawhich is the third state of the area, which has previously had a burning state and which has been extinguished with a liquid that has a chemical compound ensuring that the area cannot re-enter the burning state. This twist will totally change the Fire Fighting problem introduced by Yaniv et al. and will use concepts explained in GUARDIANSand SWEEP. To get a better grasp of our Fire Fighter problem, we want to develop a simulation for the problem that is as close towards the mathematical definition as possible. There are, however, some elements that needs to be discussed in this thesis but will not be implemented in the actual simulation because they are either assumed to be solved or abstracted away and does not contribute to the Fire Fighter problem solution. Even though these elements are not relevant to the solution of the problem, we still need to discuss them to further make our problem more realistic towards the actual real world application.

Revisiting our epidemic example of real world applications which is quite similar to the Fire Fighting application. A damaged area in this context could be interpreted as groups of people that are immune to a virus that is spreading in a community. The groups of people are separated in a geographical manner and the virus may only spread one group that is adjacent to its current contaminated group. Suddenly the epidemic application seems not so different from the Fire Fighting application which describes how much realistic thedamaged area makes the applications when adding the concept to it.

1.4 Research Questions

We will now discuss some crucial research questions that we will answer in the rest of the thesis. These questions will function as driving forces that will forward the thesis towards a reasonable result.

Having real world applications to our problem helps us understand the problem in a realistic way and therefore we may utilize concepts we

(20)

6 1. Introduction introduce in this thesis in real world scenarios. By doing this we still need to take into account for some real world dilemmas and our focus for this thesis will be the damaged area and how it will affect the cleaning problem presented in Tapia Tarifa’s and Yaniv’s et al. works [1] [4]. We now define a hypothesis that we want to prove and see how the damaged area will affect the previously defined problems by Tapia Tarifa and Yaniv et al. and will be described as follows:

"The damaged area will help the agents to completely extinguish the fire in an environment where the burning area grows."

We want to set this as our main hypothesis because it would be interesting to know in what degree such a seemingly small difference may have an impact on the problem.

Our thesis will take inspiration from the SWEEP and CLEAN protocol as mentioned in the related work section. The SWEEP protocol is solely based on solving a problem in a dynamic environment while CLEAN is based on solving a problem in a static environment. Because our own protocol will be based on these two protocols, other than to answer our hypothesis we want to introduce a research question as follows:

"How much adaptation is needed from theSWEEPandCLEANafter introducing the damaged area?"

To find this out we will need to build our own protocol and compare the differences against the SWEEP and CLEAN protocols.

1.5 Structure of this Thesis

The rest of this thesis is organized as follows:

• Chapter 2 explains the termonology we will use and introduces the Fire Fighter problem.

• Chapter 3 explains what tools we are using and why those tools fit our needs. The chapter also discusses how we developed a simulation of the problem to further gain a better understanding of it.

(21)

1.5. Structure of this Thesis 7

• Chapter 4 builds upon chapter 3 directly by introducing testing tools to ensure certain formulae introduced in chapter 2 in the simulation.

• Chapter 5 wraps up the project with observations and results gained from developing the simulator.

• Chapter 6 concerns future works of the project, extensions to theFire Fighter problem that may get implemented to the simulation at a later date.

(22)

(23)

Chapter 2 Problem

In the following sections we will define the Fire Fighterproblem and our limits to the real world Fire Fighter application. We will define how a forest may get represented, how our robots may behave and also the properties of the fire. Some other known protocols have been introduces earlier in other related works, so we will also take a closer look at them and see how we may use this knowledge to our advantage. What differentiates this thesis to other works is the properties of the damaged area so we also need to introduce this element to the problem. Most of the following definitions are taken and reused from related works mainly from Yaniv et al. [7]

2.1 Hybrid Environment

Our environment in ourFire Fightersapplication is a forest area that isn

×m size. The forest consists of masses of trees that are highly flammable.

The concentration of trees are the same in the whole forest and ground is also a flat surface and it would take the same amount of time for an agent to move between adjacent areas of the forest. The forest is on fire where the fire area is less thann × m size and can have any arbitrary shape.

We define a hybrid environment as a context that switches between being a static and dynamic environment. Static environment does not change by itself meaning that only third party agents may change it by interacting with it. In our case a static environment forest fire does not spread at says in the same area without getting influenced by time. On the contrary we have dynamic environments where the context is ever changing proportional to time. In the dynamic environment the fire may spread exponentially

9

(24)

10 2. Problem proportional to time.

2.2 Forest Grid

We represent the forest as a two-dimensional graph and contains certain traits such as states and size. We define the forest as following: letG(V,E) be an undirected graph of the forest whereV is the set of vertices in G,E is the set of edges in G [1]. Let vertex v ∈ V where v represents an area in the forest and the size of this area is as far as the robot can see with its sensors. All vertices represents the same size area. G(V,E) for V also has a two-dimensional grid which is represented with integer coordinates Z². In addition the vertices in V have a state which can be eitherburning, damaged or standing. An example of this notation, where size of Z would be 7x7 which means that Z[3,3] which refers to the third vertex to the right and down from the upper left border ofG. Z[3,3] also returns the vertex to the very center ofG. Lett be a an index number ranging from 0 ton where n is the time state when the goal has finished and the task terminates. Let function state_t(v) return which state vertex v is at t time. Both protocols that we looked at earlier requires that theburned area to be connected. We define a single connected graph as a graph where we can visit every single vertex in the burning area regardless of the starting position. Let F_t, the forest fire graph, be a single connected sub-graph of G and be defined as following:

Ft = {v ∈ G| statet(v) = burning}

Each square or vertex may contain any number up to k agents simultaneously. Wherek is the number of agents in the whole forest. This means that we define each vertex to be abstract enough so that they may have enough room for all agents used in a given configuration.

2.3 Graphical Representation of the Problem

Throughout the thesis we will be looking at many figures that illustrates the flow of the simulation. Figure 2.1 shows a squared map where:

• The whole forest is a 7x7 grid

• The green squares represents areas that are still standing and have never been burning nor been visited by any agents.

(25)

2.3. Graphical Representation of the Problem 11

• The orange squares represents areas that are burning.

• The gray squares represents areas that aredamaged. These have been burning in the past and have also been visited by an agent.

• The most top small blue square represents a single agent.

• The most bottom square with a number 2 describes two agents that are visiting the same area. The number may be higher than 2 as well meaning more than two agents may be on the same area.

• Note that the priority of each agent is abstracted away in the figures and will rather be presented thoroughly through explanations.

Figure 2.1: Processing figures explanation

(26)

12 2. Problem

2.3.1 Time

In order to distinguish fire spreading and agent movement in our system we need a concept of time. For simplicity sake we keep our system to a deterministic level and therefore we decide to have a turn-based time system as our time mechanic. Our turn-based time makes us able to approach the problem in a deterministic manner so that each execution returns an output based on the input alone. Furthermore we will define our concept of time as turn-based which means that all operations can be represented as a stack of instructions. An example of such a stack is shown in table 2.1 where two agents, a1 and a2, moves in each of their x and y axis of the forest and the fire spreading rate is d = 5 from t = 1, d being the fire spread rate.

The agent numbering in table 2.1 represents the priority of the agents. The move function takes a vertex from Z as argument which again needs indexes represented as coordinates that the agent is currently standing on and the coordinates that the agent is moving to.

t Instruction 0 a1 move(Z[1,2],Z[1,3]) 0 a2 move(Z[1,2],Z[2,2]) 1 spreadAll(F) 1 a1 move(Z[1,3],Z[1,4]) 1 a2 move(Z[2,2],Z[3,2]) 2 a1 move(Z[1,4],Z[1,5]) 2 a2 move(Z[3,2],Z[4,2]) 3 a1 move(Z[1,5],Z[1,6]) 3 a2 move(Z[4,2],Z[5,2])

Table 2.1: Example of an instruction stack

Let t be a variable for each step of the agents movement where t = 0 is the initial state of the agent. Our agents terminates when they have accomplished their goal which is to extinguish all the fire in the forest, this will happen when Ft = ∅. We define this state as the goal state when t = n where n is a finite whole number. Since n can only be a finite number, the goal state is only possible if the problem is solvable therefore our agents may never terminate if the problem is not solvable, meaning n is infinite

2.3.2 Edges

Edges are borders between vertices in the forest, therefore because we have defined a set of vertices to be neighbours to one and another. We define

(27)

2.4. Definitions 13 edges as pointers where a vertex contains pointers to other vertices. The edges are symmetrical and undirected which means that if vertex A points to vertex B then vertex B also points to vertex A.

It is important to note that in this thesis that the termedge has two different meanings. However on this thesis we will distinguish between the termedge andborder whereedge is the pointer from one vertex to another. The term border, meaning the edges that points from a vertex with one state to a vertex with a different state. An example is shown in figure 2.2 where thick lines represents the borders.

Figure 2.2: Illustration of borders

2.4 Definitions

For the rest of this thesis we will use similar definitions as Tapia Tarifa’s in her thesis¹. The reason being that the definitions makes our terminology easier to understand without losing any complexity integrity’s.

2.4.1 8-neighbors

The 8-neighbors of any vertex is the set of vertices which corresponds to all adjacent vertices horizontally, vertically and diagonally. We define the agents so that they may only see and know what’s around them in the 8- neighbors, but since we want the agents to keep their simplicity the agents viewing range is always limited. We want to define a function8-neighbors(v) that returns the set of vertices that is in the8-neighbors of vertexv. Figure

1Definitions are found at page 6 in [4]

(28)

14 2. Problem

Figure 2.3: 8-neighbor illustration

2.3 shows a blue area where all of its 8-neighbors are orange squares.

2.4.2 4-neighbors

The 4-neighbors of any vertex is the set of vertices which corresponds to all adjacent vertices horizontally and vertically so that 4-neighbors ⊂ 8-neighbors. Every vertex contains a list of edges that points to its 4- neighbors. Note that vertices does not need edges to their8-neighbors since we can find the 8-neighbors through its 4-neighbors for any given vertex.

This also means that the cardinality of the8-neighbors set is always higher than the4-neighbors set. Even though the agents may see and know what’s around them in their8-neighbors, the agents can only move around in their 4-neighbors with one step at a time. The direction of the agents can move may be defined as a set of directionsD ={down, left, up, right} [1]. When an agenta"stands" on a vertexv it will have the same pointers asv meaning that thea’s8-neighbors andv’s8-neighbors are always the same. Whenever agent a moves one step towards a direction visiting a new vertex in its 4- neighbors using a direction in D, it will also change 8-neighbors pointers to that of the vertex it is visiting. As with the function 8-neighbors(v), we also want to define a function4-neighbors(v) that returns the set of vertices that is in the4-neighbors of vertex v.

Figure 2.4 shows a blue area where all of its4-neighbors are orange squares.

(29)

2.5. Fire Extinguishing Agents 15

Figure 2.4: 4-neighbor illustration

2.5 Fire Extinguishing Agents

Our robots has no central controller but rather are autonomous entities that follows a pre-installed algorithm and does not communicate with each other. However they can predict each others behaviour, because they are running the same algorithm and they know that all other robots run the same algorithm.

When approaching problems like the Fire Fighting problem or cleaning problem we need to define the agents in a proper way. In the real world the agents may be robots with arms and legs that walks around with limited amount of supplies to extinguish fire or they might even be humans bluntly following a protocol. However these kinds of questions is not something we are going to consider, therefore they are abstracted away from the problem.

2.5.1 Memory

We define the agents to remember very few things about its context, having a simple data structure for the execution of their movement algorithm. The robots goal is to extinguish all fire in the forest. However, they do not have any prior knowledge to the forest except that the forest fire is a single connected graph. This way, the agents know that it only needs to traverse burning vertices in order to extinguish the whole fire pattern. Following the concept of swarm intelligence, all the robots are built the same and run the same algorithm and are completely independent [1]. To be able to distinguish the robots so that they may coordinate to take different routes,

(30)

16 2. Problem we need to give them some sort of a priority. Example, if two robots starts at the same coordinates we want to decide that one robot goes one way while the other goes to the opposite direction to cover more area. The agent may only remember their position in the forest and their priority compared to the other agents. This keeps the agents integrity of simplicity intact. Java code of the attributes may be represented like this:

c l a s s A g e n t { V e r t e x c u r r e n t ; int p r i o r i t y ;

D i r e c t i o n p r e v i o u s ; b o o l e a n t e r m i n a t e d ; }

Listing 2.1: Agent basic memory attributes

The previous attribute in listing 2.1 represents the previous direction the agent moved which will be utilized for it to make a decision towards its next movement. These attributes will be further explained in chapter 3.

2.5.2 Movement

Restrictions to agent movements are set so that they may be represented in a context of simulation with a realistic approach. If we had contrary concept of a super agent that could move by teleporting or jumping around the forest, we would need to have a reasonable explanation of how we could do that in real life which is impossible. Here are some rules that we set to our agent movement to enhance their simplicity and be more feasible to the real world application:

• The agents may only move from one vertex to one of the 4-neighbor of the vertex that the agents is currently standing on. Therefore an agent may not move diagonally and only one step at a time.

• The agents may only move one step at a time meaning it cannot move two steps within an interval oft =t + 1.

• The agents may not move to a vertex that is not burning.

• The agents may read the states of all vertices in its 8-neighbors

(31)

2.6. The Damaged Area 17

2.6 The Damaged Area

The damaged area, unlike some other concepts mentioned in this thesis, is a new concept in this thesis. We define a damaged area as a vertex that leaves the burning state by being extinguished. There may be more than onedamaged areas caused by the same or different agents. The vertices that has this state is special because they cannot enter theburning state again.

In the real world application we can explain this concept with for example the robots using an extinguishing liquid that makes it hard to ignite an area twice once the liquid is sprayed onto the area. Let’s say that a vertex with the burning state may enter the damaged state with time and without any agents affecting it since this may be more realistic towards real life forest fires. However this will endanger the integrity of the connection between the two protocols and our problem. With the protocols demanding that graph F_t stays a single connected graph this may be ruined if a critical point goes from burning to damaged outside of the agents control. Now we have a lot of knowledge about the problem when the environment has a dynamic state so that we can present the damaged area, but before we dig into this crucial element in our problem, we want to define some more concepts [7]:

• Complete extinguishing: This concept can be formalized as F_t_success =∅.

• Agreement on Completion: If and only if time t reaches t_success then all the agents will stop.

• Solvable Condition: If and only if {w|state(w)∈ {burning, damaged}

and w ∈ 4-neighborhood(v) for all v ∈ F_t} then we know that completion is possible. In other words, if all 4-neighbors of all the burning vertices is either burning or damaged, then we know the problem is solvable.

The first two concepts are similar to the ones defined in Yaniv’s et al.

work [1]. For theFire Fightingproblem, we want to minimize the amount of damaged area when full extinguishing is possible and this area will be critical for the paradigm shift with the environment going from a dynamic to a static environment. We consider the damaged area to be non-flammable, which means that once an area becomes a damaged area, it cannot be lit on fire again. By utilizing the SWEEP protocol on a fire we will end up having an encapsulated fire that doesn’t spread once the agents have extinguished the circumference of the fire.

(32)

18 2. Problem Because of how an agent leaves behind adamaged area after extinguishing a burning vertex, we know that the vertex may never enter theburning state more than one time. By introducing this concept to the problem concerned in Yaniv’s et al. work, we may solve problems with parameters that would be impossible to solve for the SWEEP protocol solve [1].

2.7 Fire Spread

In this thesis we will define a deterministic concept for fire spreading because it makes our system easier to predict although it will lessen our scope to the real world application of fire spreading. Every execution of the system with the same parameters will be the same, hence the easier predictability.

A deterministic approach of fire spreading where we assume that the fire may only spread to all of its4-neighbors at interval m wherem is a whole positive number.

We do this to make the problem simpler, and as discussed earlier, so that the problem still may be comparable to other real world applications that utilizes the same concepts of a hybrid environment. Now we formalize a general concept of impossibility that links fire spreading and extinguishing together. Listing 2.2 shows the procedure that is upon called for all vertices in the forest. The procedure takes an incoming vertex v and returns if the state of v is not burning, otherwise it changes the state of the 4-neighbors inv to burning.

1: procedure SpreadFire(v) . v is the current vertex to spread its fire

2: if v.state 6=burning then

3: return

4: end if

5: for each x∈v.f ourN eighbors do

6: x.state=burning

7: end for

8: end procedure

Listing 2.2: Algorithm for spreading fire

(33)

2.7. Fire Spread 19

Figure 2.5: Fire spread illustration

Figure 2.5 demonstrates how fire can spread in an exponential rate if not extinguished in time much like real life forest fires. The first model shows a single vertex in the very center of the forest that then spreads itself to its4- neighbors shown in the second model. It is important to note that the first spread is also the step that spreads the most proportionate the previous fire size. In figure 2.5 the first spread makes the fire five times larger than its previous size and is also the absolute worst case for the given fire pattern.

This means that if a configuration of agents fails to extinguish the single vertex the work load will quintuple itself.

(34)

20 2. Problem

2.8 Critical Vertex

Since the agent may only traverse on burning vertices we need to define a rule where an agent may not extinguish aburning vertex so that the agents will never split F_t into two or more sub-graphs. We call this concept a critical vertex and all critical vertices may be defined as the following set in a graph:

Listing 2.3: Critical vertex mathematical representation

X_t = {v ∈ G | squareCount( v ) < f ourN eighborBurnCount( v ) − 1}

Y_t = {v ∈ G | squareCount( v ) < 4}

Z_t = {v ∈ G | f ourN eighborBurnCount( v ) > 0}

C_t = X_t ∩ Y_t ∩ Z_t

Here we have three predicates in listing 2.3,X_t, Y_t and Z_t, that all need to be true to determine if a vertex is acritical vertex. PredicateX_tcounts how many 2x2 squares that areburning in8-neighbors in vertexv and compares it to the4-neighbors that are also burning. Y_t checks the squareCount that is burning in vertex v while Z_t makes sure that at least one of 4-neighbors in vertexv must be burning forv to be a critical vertex. This concept will be further explained in section 3.4.

(35)

Chapter 3 Solution

In this chapter we will further look at some observations made when executing the system and solving the problem. We will see what occurs when actually making an implementation of the system. After this chapter, we will explain what elements introduced in chapter 2, which made the problem easy and what made it hard.

3.1 Related Protocols

3.1.1 SWEEP

Yaniv et al. in their work utilize a protocol to solve Dynamic Cooperative Cleaners problem named SWEEP. They define SWEEP as following:

having a connected graph called the contaminated graph where whenever an agent cleans a vertex, they also delete the vertex and the goal being that the graph becoming empty. To prevent disconnection of the graph, they set specific rules so that any agent that enters vertices that arecritical, cannot clean and have to continue onwards. The pattern for the agent movement is in a spiral matter starting from the borders, "peeling layers from the shape" as they mention. Having multiple agents working together changes their movement a bit by having one agent move one step further inside the layer of the shape rather than moving on the same vertices [1]. The Fire Fighter protocol will also do the same except that we will rather have every other agent go in different directions which is further explained in subsection 3.6.1.

21

(36)

22 3. Solution

Figure 3.1: SWEEP protocol from Yaniv et al. [2]

To be able to develop our very own algorithm to solve our variation of the problem we need to have a better understanding of SWEEP. By knowing

(37)

3.2. Simulation 23 SWEEP by detail and how it functions on the cleaning agents we will save a lot of work and we will be able to reuse many concepts in our own algorithm because the problems still has many common features. Figure 3.1 shows a pseudo code of the protocol SWEEP which illustrates how each agents cooperate and cleans a given pattern with only the the start coordinates, which are represented as pairs of x and y integers, as input arguments.

3.1.2 CLEAN

Tapia Tarifa focuses on a static environment in her thesis using theCLEAN protocol [4] which solves a similar problem as our hybrid. Yaniv et al. also works withCLEAN in their work when definingSWEEP. Her algorithm does not need to handle any contamination spreads like ours do which is the main difference betweenSWEEP and CLEAN.

3.2 Simulation

A prototype simulation tool was written for this thesis as a project to further visualize and test the system [3]. It was written in Java and using Processing to visualize the system behavior to get a clearer grasp of the different concepts [12]. By developing a program as the prototype simulation tool we are able to feed the program inputs and get outputs in return, we define these inputs as configurations since there are many different types of inputs such as shapes of the forest and numbers of agents.

3.2.1 Java

Java is an object-oriented programming language and is, as of this writing, the most used programming language in the world [13]. Object-orientation is a central concept in Java and cannot be avoided when programming with it. It also supports parallel programming with threads. Since it got such a large user base, there is a lot of support for the language. Packages and libraries included in the language makes programming easy and saves a lot of time without damaging our prototype simulator but rather could help our prototype simulator clearer and better defined.

Our motivation for using Java comes from Java being a highly imperative and object-oriented language [14]. This means that programs in Java are easily expandable which again means we will be able to write big programs that utilizes complex data structures. The key feature to easily expanding a program is an important trait when it comes to a project as described in

(38)

24 3. Solution this thesis as seen in the future work chapter, there will be many features that may get expanded upon further in the future. Working with an object- oriented programming language also forces a developer to think organized and create a understandable model.

For visualization, we use a game engine called Processing which may be programmed in Java or in other programming languages such as C# [12].

Processing is an easy to learn and efficient tool for drawing and illustrating objects in 2D. This engine enables us to write Java code that will represent a front-end for our simulation meaning that we will only need to know one language for the whole simulation which saves us time and resources.

Objects in Java are represented as a class with a set of attributes, methods and constructors. Attributes are declared with a specification of the type of the attributes as seen in listing 3.1age and name is declared to only be assigned to anint and aString. Primary types and objects are distinguished in Java with capitalizing the typename which means thatint is a primary type that is assigned to a variable whileString being an object which means that age is a pointer that may point to an object.

(39)

3.2. Simulation 25

1 p a c k a g e u q t r a n ; 2

3 i m p o r t u q t r a n . u t i l s . V e r t e x U t i l ; 4 i m p o r t s t a t i c u q t r a n . S t a t e .*;

5 i m p o r t s t a t i c u q t r a n . D i r e c t i o n .*;

6

7 p u b l i c c l a s s A g e n t { 8 V e r t e x c u r r e n t ; 9 int p r i o r i t y ;

10 D i r e c t i o n p r e v i o u s ; 11 b o o l e a n t e r m i n a t e d ; 12

13 /*

14 * S o m e c o m m e n t a b o u t the c o d e he r e 15 * C o m m e n t s g e t s i g n o r e d by the c o m p i l e r

16 */

17

18 A g e n t (int p r i o r i t y , V e r t e x s t a r t V e r t e x ) { 19 t h i s. p r i o r i t y = p r i o r i t y ;

20 t h i s. c u r r e n t = s t a r t V e r t e x ; 21 t e r m i n a t e d = f a l s e;

22 }

23

24 p u b l i c v o i d m o v e (int d i r e c t i o n ) {

25 V e r t e x n e x t V e r t e x = c u r r e n t . g e t F o u r N e i g h b o r s () [ d i r e c t i o n ];

26 if( n e x t V e r t e x == n u l l) {

27 r e t u r n;

28 }

29 c u r r e n t = n e x t V e r t e x ;

30 }

31

32 p u b l i c b o o l e a n s h o u l d T e r m i n a t e () {

33 V e r t e x [] f o u r N e i g h b o r = c u r r e n t . g e t F o u r N e i g h b o r s () ; 34 for(int i = 0; i < f o u r N e i g h b o r . l e n g t h ; i ++) { 35 if( f o u r N e i g h b o r [ i ] != n u l l) {

36 if( f o u r N e i g h b o r [ i ]. g e t S t a t e () == B U R N I N G ) {

37 r e t u r n f a l s e;

38 }

39 }

40 }

41 r e t u r n c u r r e n t . g e t S t a t e () != B U R N I N G ;

42 }

43

44 /*

45 * @ O v e r r i d e

46 */

47 S t r i n g t o S t r i n g () {

48 r e t u r n " a g e n t " + p r i o r i t y + " is c u r r e n t l y in " + c u r r e n t . g e t C o o r d i n a t e T e x t () ;

49 }

50 }

Listing 3.1: Java code example

(40)

26 3. Solution Methods are defined with the signature and tokens as shown in listing 3.2.

The parameter list is represented at attribute declarations separated by commas and may be used as initialized attributes in the declaration list.

Constructors has a slightly different signature in that its name needs to be the same as the class name that it is tied to and it cannot return anything.

However constructor do otherwise function the exact way as methods and it executed as soon as an object of the class is created. The interface of this class therefore consist of line 1, 3-5, 7-11, 18, 24, 32 and 47 where each line describes different elements of the interface. Line 7 defines the name of the class which is "Agent", line 3 to 5 declares the attribute variables with their type and the name of the variable. Line 18 defines the parameter list of the class constructor and finally, line 24, 32 and 47 defines the class methods with the return type, name and parameter list for the methods.

Line 26 makes use of theOverride annotation and ensure that the method toString in the classObject, which is a class that all classes in Java extends, gets overwritten with the method in line 47 [15].

<r e t u r n type > < n a m e of method >( < p a r a m e t e r list >) {

< s t a t e m e n t list >

}

Listing 3.2: Java method signature

In our implementation we want to separate the simulations into two programs. The first program reads any given configuration, solves the problem based on the configuration and then shows the results in the terminal in real time. The other program is intended to read the results and visualize the problem, giving us a whole different perspective on the problem which makes it easier for us to analyze the given configurations.

3.3 Data Structure

When working with Java as our main tool, we need to work with our problem by defining a good data structure because Java is mainly an imperative programming language. On the contrary we could have used a more functional programming language such as Lisp that could make our code more compact and abstract away some unnecessary aspects such as types and splitting up operations into multiple functions. The main

(41)

3.3. Data Structure 27 reason we chose to approach the problem in an imperative way is to force ourselves to define a proper data structure that can later easily be extended and redefined if needed such as implementing anything from the future work chapter.

3.3.1 Vertex Definition

The source code in listing 3.3 shows how we implement a proper data structure for a forest vertex as well as how we utilize Java enum classes for declaring the different types of states. The source codes contains the attributes, initializations and the functions needed for the environment and third party agents to be able to interact with the vertices described in the Problem chapter. Here are some explanation of the attributes and functions¹:

• the pointer state represents the state that the vertex is currently in.

• the variablesposX andposY represents the coordinates of the vertex.

The coordinates are unique to each vertex and therefore they are final and will never change.

• the array fourNeighbors contains a list of pointers which point to vertices which are directly adjacent to a vertex and always has a cardinality of 4. If a vertex is on the bounds of the forest, then fourNeighbors may contain pointers that points to null.

• when running the listing 2.2 we need to iterate through the two- dimensional forest grid with two for loops, each loop for each dimension. As we spread our fire we quickly realize that we do not want to spread a vertex that has newly changed state to burning hence we toggle thepreBurn switch to indicate that the current vertex cannot spread it’s fire even though it has aburning state.

• the function burn is called on by other vertices that needs to spread it’s fire.

• the function extinguish is called on by the agents.

• the function getBurningNeighborCount returns the number of 4- neighbors which state is burning.This function used to check critical vertices.

1The source code of the prototype simulator can be found athttps://github.com/

UyQTran/FireFighters[3]

(42)

28 3. Solution

e n u m S t a t e {

burning , s t a n d i n g , d a m a g e d ; }

c l a s s V e r t e x { S t a t e s t a t e ;

f i n a l int posX , p o s Y ; V e r t e x [] f o u r N e i g h b o r s ; b o o l e a n p r e B u r n ;

V e r t e x ( S t a t e state , int posX , int p o s Y ) { t h i s. p r e B u r n = t r u e;

t h i s. s t a t e = s t a t e ;

t h i s. f o u r N e i g h b o r s = new V e r t e x [ 4 ] ; t h i s. p o s X = p o s X ;

t h i s. p o s Y = p o s Y ; }

p u b l i c v o i d b u r n () { s t a t e = S t a t e . b u r n i n g ; }

p u b l i c v o i d e x t i n g u i s h () { s t a t e = S t a t e . d a m a g e d ; }

p u b l i c int g e t B u r n i n g N e i g h b o r C o u n t () { int c o u n t e r = 0;

for(int i = 0; i < f o u r N e i g h b o r s . l e n g t h ; i ++) { if( f o u r N e i g h b o r s [ i ]. s t a t e == S t a t e . b u r n i n g ) {

c o u n t e r ++;

} }

r e t u r n c o u n t e r ; }

}

Listing 3.3: Data structure for Vertex and State

(43)

3.3. Data Structure 29

3.3.2 Forest Definition

Our Forest class Java handles all logic that is related to the forest grid as a whole.

• the two-dimensional array graph, represents the whole forest as a rectangular shape. We choose to implement the forest itself as a rectangle to be able to minimize the memory needed to fit any contaminated shape into the forest.

• the ArrayList burningArea contains all the burning vertices in graph and representsF_t, the contaminated graph. This ArrayList is mainly used to choose an arbitrary vertex for the agents to start on.

p u b l i c c l a s s F o r e s t { V e r t e x [ ] [ ] g r a p h ;

A r r a y L i s t < Vertex > b u r n i n g A r e a ; F o r e s t (int sizeX , int s i z e Y ) {

g r a p h = new V e r t e x [ s i z e X ][ s i z e Y ];

b u r n i n g A r e a = new A r r a y L i s t < Vertex >() ; i n i t () ;

} }

Listing 3.4: Data structure for Vertex and State [3]

Listing 3.4 shows how the simulation initializes the whole forest. The first double nested for-loop initializes all the vertices in the forest by creating and assigning a Vertex object to each graph-pointer. We also pass all necessary parameters that each Vertex needs including unique coordinate combinations and initial states when initializing an object.

Pointers in Java may only carry the reference to an object and not other pointers. This means that reassigning a pointer to a new reference does not change any other pointers than the reassigned pointer. Example, if we assign pointer A to object C and pointer B to A then reassign A to object D, we do not change whatever pointer B was pointing at. This happens in Java because whenever assigner a pointer to point to another pointer, we only assign the reference to the object of that pointer. Because of how

(44)

30 3. Solution pointers work in Java, we are forced to loop through our forest grid twice, once to initialize all the vertices and the second time we need to assign all the 4-neighbors in each of the vertices.

p r i v a t e v o i d i n i t () {

for(int i = 0; i < g r a p h . l e n g t h ; i ++) { for(int j = 0; j < g r a p h [ i ]. l e n g t h ; j ++) {

g r a p h [ i ][ j ] = new V e r t e x ( S t a t e . s t a n d i n g , i , j ) ; }

}

for(int i = 0; i < g r a p h . l e n g t h ; i ++) { for(int j = 0; j < g r a p h [ i ]. l e n g t h ; j ++) {

V e r t e x c u r r e n t = g r a p h [ i ][ j ];

if( i > 0)

c u r r e n t . f o u r N e i g h b o r s [ Dir . L E F T ] = g r a p h [ i - 1 ] [ j ];

if( i < g r a p h . length -1)

c u r r e n t . f o u r N e i g h b o r s [ Dir . R I G H T ] = g r a p h [ i + 1 ] [ j ];

if( j > 0)

c u r r e n t . f o u r N e i g h b o r s [ Dir . UP ] = g r a p h [ i ][ j - 1 ] ; if( j < g r a p h [ i ]. length -1)

c u r r e n t . f o u r N e i g h b o r s [ Dir . D O W N ] = g r a p h [ i ][ j + 1 ] ; }

} }

Listing 3.5: Forest initialization [3]

All fire spread logic is shown in listing 3.6 with a main fire spreading method, spreadFire, with its helping methods. The methodspreadFire contains two doubly nested for-loops. The first loops spreads all fire that has not been spread in the current step to its 4-neighbors. This is done by having a helping boolean variable preBurn that will stop spreading of any fire that was spread during the same step. The second double nested for-loops resets the preBurn variable for the next iteration of fire spread.

(45)

3.3. Data Structure 31

p u b l i c b o o l e a n s h o u l d B u r n (int x , int y , int dir ) {

V e r t e x v e r t e x = f o r e s t G r i d [ y ][ x ]. g e t F o u r N e i g h b o r s () [ dir ];

if( v e r t e x == n u l l) { r e t u r n f a l s e; }

S t a t e v e r t e x S t a t e = v e r t e x . g e t S t a t e () ; r e t u r n v e r t e x S t a t e == S T A N D I N G ;

}

p u b l i c v o i d b u r n V e r t e x (int x , int y , int dir ) {

V e r t e x v e r t e x = f o r e s t G r i d [ x ][ y ]. g e t F o u r N e i g h b o r s () [ dir ];

if( v e r t e x == n u l l) { r e t u r n;

}

v e r t e x . b u r n () ;

b u r n i n g A r e a . add ( v e r t e x ) ; v e r t e x . p r e B u r n = t r u e; }

p u b l i c v o i d s p r e a d F i r e () {

for(int i = 0; i < f o r e s t G r i d . l e n g t h ; i ++) { for(int j = 0; j < f o r e s t G r i d [ i ]. l e n g t h ; j ++) {

if( f o r e s t G r i d [ i ][ j ]. g e t S t a t e () == B U R N I N G

&& ! f o r e s t G r i d [ i ][ j ]. p r e B u r n ) {

if( i > 0 && s h o u l d B u r n ( i , j , L E F T . g e t V a l u e () ) ) b u r n V e r t e x ( i , j , L E F T . g e t V a l u e () ) ;

if( i < f o r e s t G r i d . length -1 && s h o u l d B u r n ( i , j , R I G H T . g e t V a l u e () ) )

b u r n V e r t e x ( i , j , R I G H T . g e t V a l u e () ) ;

if( j > 0 && s h o u l d B u r n ( i , j , UP . g e t V a l u e () ) ) b u r n V e r t e x ( i , j , UP . g e t V a l u e () ) ;

if( j < f o r e s t G r i d [ i ]. length -1

&& s h o u l d B u r n ( i , j , D O W N . g e t V a l u e () ) ) b u r n V e r t e x ( i , j , D O W N . g e t V a l u e () ) ; }

} }

for(int i = 0; i < f o r e s t G r i d . l e n g t h ; i ++) { for(int j = 0; j < f o r e s t G r i d [ i ]. l e n g t h ; j ++) {

f o r e s t G r i d [ i ][ j ]. p r e B u r n = f a l s e; }

} }

Listing 3.6: Burn methods and helping methods [3]

(46)

32 3. Solution

3.4 Identifying Critical Vertices

Critical vertices plays a big role in the simulation of the problem. Whenever an agent steps unto a vertex it must analyze its current state and also analyze the neighbor vertices as well in order to get enough information to preserve graph connectivity in F_t. By solving these challenges we ensure that our simulation becomes stronger and will also increase the agents efficiency.

To check for critical vertices we need to count how many 2x2 squares that are burning and compare it to how many 4-neighbors are burning. The reason why we are counting 2x2 square is because we know that we can visit and extinguish all the burning squares in the graph regardless of the agent’s position within the 2x2 graph. Listing 2.3 showed that X_t utilizes this very property with the 2x2 grid by stating that v is critical if the amount of squares that v is part are less than the amount of 4-neighbors that v has - 1. By that X_t takes into account for 3x3 grid like shown in figure 3.2 and will ensure that every burning 4-neighbor is a part of a 2x2 burning grid. The Y_t makes sure that the square count of v is less than 4 because we know that 4 is that most squares that v can be in, while Z_t ensures that v has at least one or more 4-neighbor because if v has no 4-neighbors then it is the only burning vertex in F_t and is thereby not a critical vertex.

Figure 3.2: Critical vertex example

Figure 3.2 shows an example of a vertex in the center of the grid, Z[3,3]

that is critical. This means that if an agent would start on Z[3,3], it would not be able to extinguish the vertex right away. Using what we now know about critical vertices we may count amount of squares in figure 3.2 which

(47)

3.4. Identifying Critical Vertices 33 counts to 2 squares while vertex Z[3,3] has four 4-neighbors which fulfills all predicates for the critical vertex C_t.

3.4.1 Loops

One of the problems we encounter is that when all vertices in the graph F_t contains critical vertices which means that F_t is a ring. Then our agent finds itself stuck in a loop where it cannot extinguish any vertices and the task becomes impossible to solve. To this, we consider Yaniv’s suggested solution which is to have our agent remember four different flags [2]:

• Not extinguished a single vertex since last time the agent visited the maximal vertical coordinate of the shape.

• Not extinguished a single vertex since last time the agent visited the maximal horizontal coordinate of the shape.

• Not extinguished a single vertex since last time the agent visited the minimal vertical coordinate of the shape.

• Not extinguished a single vertex since last time the agent visited the minimal horizontal coordinate of the shape.

If all of these flags are true at the same time, the agent extinguishes its current vertex, hence destroying the ring and then continues with its algorithm as normal. This solution is not quite optimal when it comes to performance and efficiency because we need to traverse the ring twice which may be a difficult and time consuming task for the agents when dealing with really big rings. The first time the agents traverse the ring they get to know which vertex is the minimal and maximal coordinates of the shape and the second time they get to revisit the minimal and maximal coordinates and lifting the flags. The flags are handled by the agents just remembering four different coordinates minimum of x, minimum of y, maximum of x and maximum of y. The problem with delaying the extinguishing like Yaniv’s solutions is that the shape may change while the agents tries to identify the minimum and maximum of x and y.

(48)

34 3. Solution

3.4.2 Efficiency of Identifying Loops

Efficiency plays a trivial role in some cases but may suddenly become a crucial element when utilizing Yaniv’s suggested solution. If the fire spread rate is faster than the agent, when it traverses the shape, then the agents need to "restart" with the procedure and therefore may end up in yet another loop with the fire spread resetting the agents progression. The problem then again may become impossible if the fire rate is too high, but that may also happen with or without the agent being stuck in a loop if the fire spread rate is faster than the extinguishing rate.

3.4.3 Preventing Loops

Knowing Yaniv’s solution to solving the ring problem we quickly realize that rings are difficult to deal with and if possible, we want to prevent rings entirely. Even though we want to prevent rings and therefore prevent the use of Yaniv’s suggested solution for the earlier mentioned reasons, we still need to utilize it if F0 initially is a loop and our agents has no choice other than to handle the ring. We then define a solution to prevent creations of rings by our agents when t > 0. Our solution will also exploit the very crucial property of the damaged area, which is that the damaged area cannot burn.

3.4.4 Junctions

Junctions are sets of vertices where there are more than one path for an agent to go. For example if we have a linked list as F_t and two agents start anywhere but the end of the linked list they face a junction and would need to split up in a way so that the linked list may get extinguished efficiently.

A key property of a junction is that it contains one single vertex that is in its very center. We call this vertex acore junction vertex. This vertex is what connects the different paths together. Letv ∈FtandgetBurningVertices(g) be a function that returns the burning vertices in graph g so that w ∈ getBurningVertices(8-neighbors)\getBurningVertices(4-neighbors). Vertex v is acore junction vertex if and only ifv andw are not adjacentvertices.

3.4.5 Handling Junctions Cooperatively

To handle junctions optimally, we need to consider two crucial procedures when our agents start extinguishing a junction: identify the junction and its structure and decide who goes to which vertex. These procedures also need to maintain the integrity of the main algorithm.

(49)

3.4. Identifying Critical Vertices 35 The two earlier mentioned procedures should only be executed by the agents whenever there are two agents on the same vertex. This is because we can only optimally extinguish the junction if and only if there are the same amount of agents as there are paths going out of the junction. With one agent, we can skip this part of the algorithm, because its main moving algorithm is actually the most efficient way of extinguishing the junction.

Once the agents have acknowledged each other they may check every new vertex they step on whether or not it is a part of a junction. They check by simply looping through the list of 4-neighbors of the current vertex and counting the amount of burning vertices. When two agents meet within a junction we define a rule so that they must extinguish the current vertex even though it is critical and then they must go their separate ways to prevent extinguishing the same vertices. Compared to problems concerning loops, the only way solve the junctions problem efficiently is to utilize multiple agents meaning that there isn’t some smart implementation that can make one agent able to solve the problem more efficiently than simply traversing through the whole line.

Figure 3.3: Junction example

Two agents starts at the same coordinates where the fire creates a junction with two paths. The optimal solution for this problem is for the agents to extinguish the current vertex even if its a critical vertex and go their separate paths. This is also how we may solve ring problems cooperatively in an efficient way.

Figure 3.3 illustrates how two agents may go and solve a junction or ring problem, but in the scenario of junctions with more than two paths would require the same amount of agents to solve the problem in the same way.

If for instance a scenario with two agents and a junction with three paths was the problem, we would not be able to solve it in the same way.

When two agents face a junction with three paths, they cannot extinguish

Cooperative Fire Fighters

Cooperative Fire Fighters

Uy Quoc Ton Tran

Master’s Thesis, Autumn 2017

Cooperative Fire Fighters

Uy Quoc Ton Tran

preface

abstract

Contents

List of Figures

List of Tables

Listings

Chapter 1 Introduction

1.1 Motivation

1.1.1 Swarm Intelligence

1.1.2 Real World Applications

1.2 Related Work

1.2.1 SWEEP

1.2.2 CLEAN

1.2.3 GUARDIANS

1.2.4 SDS

1.3 The Little Twist

1.4 Research Questions

1.5 Structure of this Thesis

Chapter 2 Problem

2.1 Hybrid Environment

2.2 Forest Grid

2.3 Graphical Representation of the Problem

2.3.1 Time

2.3.2 Edges

2.4 Definitions

2.4.1 8-neighbors

2.4.2 4-neighbors

2.5 Fire Extinguishing Agents

2.5.1 Memory

2.5.2 Movement

2.6 The Damaged Area

2.7 Fire Spread

2.8 Critical Vertex

Chapter 3 Solution

3.1 Related Protocols

3.1.1 SWEEP

3.1.2 CLEAN

3.2 Simulation

3.2.1 Java

3.3 Data Structure

3.3.1 Vertex Definition

3.3.2 Forest Definition

3.4 Identifying Critical Vertices

3.4.1 Loops

3.4.2 Efficiency of Identifying Loops

3.4.3 Preventing Loops

3.4.4 Junctions

3.4.5 Handling Junctions Cooperatively