PRE2017 3 Group 17

Members of group 17
Eric Arts	1004076
Menno Hofsté	0996144
René Nijhuis	0912331
Erik Takke	1000575
David Tuin	1013331

Introduction

As commissioned by this course, it is our goal to create and execute a project that can change the lives of people around us. This project is part of a USE-course, so user orientation plays a central role. This wiki is created to show the progression of the project. On this wiki page you can read all about our project: the choices that have been made, the progression of development and much more.

Problem Statement

In building projects it happens quite often that objects are too large to be carried by man and have to be brought to their desired spot by crane. However, as the construction advances, the building gets closed of more and more, making the cranes unable to reach the desired spot. Nowadays, this problem is usually solved by using all different types of transportation to get the object to its destination. These different types of transport, and especially transitioning from one to another, takes a lot of time. To reduce the time it takes to transport objects, it would be desirable to have a single means of transport that can carry the object to its final resting place fast and in one, smooth go.

One means that comes to mind are robots. Drones in particular seem to be a good fit, as they are small, fast and really maneuverable. However, what makes drones even more suitable for the job, is that they can move from floor to floor without external assistance. Drones are not used for this type of transport just yet. To make this a reality, it is our plan to develop the software necessary to guide the drones through or around construction zones and have them deliver the object to the desired destination. It is the aim to have the drones evade obstacles (walls and scaffolding), navigate between floors (flying through elevator shafts or stairwell) and detect humans and stop or evade them, depending on what is safer.

To reach this goal, a proper problem statement has been constructed: How to move objects through buildings that are under construction, using drones.

Approach, milestones and deliverables

To reach the goal: creating software that can lead drones through a building that is under construction, several things have to be done. First of all, literary research has to be performed to see what is currently possible, what seems to become possible in the next years and what is still quite a ways out. Then it is clear where the difficulties will be and what to focus on. With that information in mind, the following plan has been made. This plan consists of a list of milestones. Once all these milestones have been achieved, the result should be that all deliverables have been constructed.

1. Create a way to read a layout of a building and represent that on screen. (achieved on 13-03)
2. Create a algorithm that can search the building for the fastest path to its destination. (achieved on 02-03)
3. Create a basic model in which drones can fly around.(achieved on 16-03)
4. Congregate above mentioned features to work together. (achieved on 19-03)
5. Expand model such that multiple drones can fly around concurrently. (achieved on 19-03)
6. Expand model such that drones do not cross each other in corridors. (achieved on 22-03)
7. Implement features to dynamically adjust the models environment. (achieved on 22-03)
8. Finalize project. (achieved on 5-04)

The goal is to create software to have the drones fly by themselves. In the end we will deliver two things. First of all, an algorithm that finds a path through the building that is under construction and can adjust its path in dynamic situations. It is our goal to create this software as realistically as possible, preferable to the point that it could be used in a real life situation. Second, to show what we have accomplished, certain example situations will be created. For these situations, the algorithm output will be explained. They can be found at PRE2017_3_Group_17_Test_Cases#Avoiding Obstacles and Actors and should give a clear view of what the developed software is capable of.

The git repository for these deliverables can be found here.

State of the Art

To keep this wiki clutter free, the page State of the Art has been created, containing several articles that support the attainability of this project. In addition to this state of the art research, two interviews were conducted. These interviews were held with construction workers who are working at the Atlas building on the TU/e campus. Again, to keep this page clutter free, the complete interviews have been moved to interviews.

It is however useful to summarize the findings of the performed research. First of all, drones are already used at construction zones, but only to survey them, rather than assist the construction workers. Additionally, as expected, most drones are not yet capable of lifting payloads larger than 1,5KG. Even though some drones exist that can carry more, they are either very expensive or very large and therefore not suited for flying inside a construction zone. That leaves to conclude that this project would for now just be useful for delivering smaller objects. However, as technology progresses, it is expected that the payload a drone can handle will increase, allowing for delivery of larger objects and maybe even large construction materials. For now, the interviewees have shown interest in delivering small objects, such as small tools and sealant. Flying inside a building does not seem to be a big problem. Many researchers have delved into this and have succeeded. Take for instance the TU/e spinoff Blue Jay. They are capable of flying a drone inside buildings no problem.

This all leads us to believe that our project will be attainable and have an actual use once actually deployed.

Objectives

As can be read in the #Problem Statement, it is our goal to create software that can guide object carrying drones through a multi-floor construction site. To reach this goal, several objectives can be set to clearly see the progress that is made over the weeks. Some objectives directly follow from #Approach, milestones and deliverables, as a milestone could be to complete some objective.

Drone Guidance

The system is equipped with a layout of the construction zone. From this layout a graph can be manually created (see #Discussion / Reality Check), which has to be used to find the optimal path the drone will use to travel to the destination. The question remains, what is the optimal path? The opitmal path is the path that is safest, while also being the most efficient. Following are a few aspects that have to be taken into account when trying to find the optimal path.

Firstly, finding the optimal path implies finding the fastest path given the circumstances. So an objective is creating an algorithm which can find such a path.

Corridors in office buildings will be quite narrow, and could prevent drones from flying through them at the same time. To manage this, the system has to be able to make corridors one way paths only. That way (multiple) drones can safely fly in the same direction, whilst drones that want to fly in the opposite direction in the same corridor have to wait at a spacious intersection. This intersection will appear in the model with the use of special 'passing nodes'. So essentially the model has to be able to 'lock' certain edges.

The model has to incorporate obstacles. These obstacles can either be construction workers, walls, or blocks of a rectangular area. The model works under the assumption that the drone itself can detect the obstacle, while the model should make the decisions on how to react to this obstacle. This part is of utmost importance, as the collision between a drone and a human would not only lead to possible equipment failure, but could also lead to severe injury.

Just like in every construction zone, obstacles (such as scaffolding) will be moved constantly, making for a dynamic environment. The model should reflect this important aspect of real life scenarios and therefore the model has to be able to adjust its path on the fly, evade objects/obstacles and still find a path to its destination.

Create simulation

As this software relies on very advanced hardware that we do not have at our disposal flying actual drones through construction sites is not an option. Still, it would be preferred if the result could be presented such that all functionality could be showcased. Thus a simulation will be created which shows how the drones fly through an example building. This building will be similar to Atlas (a.k.a. Hoofdgebouw) on the TU/e campus currently under restoration, in that it will contain various floors, a limited amount of transitions to switch floors (E.g. staircases or elevator shafts), and relatively large floors (~50*100m). Furthermore, unlike Atlas and more like het Paviljoen (the Pavilion), there will be plenty of open spaces between rooms, as this will clearly illustrate drones favouring indoor flight over going outside. See the image below for the test building.
This simulation will also be interactive in a sense that it is possible to:

• Add / Move / Remove construction workers
• Add / Remove obstacles of various sizes
• Add a new task for a drone.
• Add a wall.

More specific information can be found at The interface.

The users

Safety Regulations

On a construction site a lot of activity takes place every day. Because many of those activities involve large and heavy machinery, safety regulations have been set in place to protect the construction workers. For each specific task performed on a construction site, a rigorous work plan has to be created, which has to be approved by the foreman. Only then can the task be performed. Tasks that are being performed constantly, for instance lifting load with a tower crane, requires workers with years of training and a sharp eye for detail. That job is completely build around restrictions and safety regulations. For instance, the crane operator has to keep an eye on the weather conditions, avoid turning the load above a construction worker and prevent collisions with a building or other tower cranes.

As this project involves the usage of drones to deliver load to construction workers, it has to be made clear what safety regulations would apply to these drones, before they can be used. Even though small drones are currently incapable of lifting loads of over 2 KGs, technology seems to catch up allowing them to do so in the near future. Just as with a tower crane, a drone could potentially drop its load or fail all together. If that drone would be high up in the air, then regardless of total weight it could potentially harm one or more construction workers if it were to fall on top of them. It is therefore necessary that flying above construction workers is avoided at all cost. Therefore the decision was made to have drones move through the building itself as much as possible. That way the potential drop height is decreased significantly, which would, in case of failure, lead to less damage to construction workers, the load and the drone.

As floor heights have been increasing over the years, a decision on how high the drones would fly through the building has to be made too. The same argument used to have the drones fly inside can be applied here too. Therefore it would be wise to have drones fly at a quite low altitude. However, when flying too low, they would be potentially be less visible to the construction workers. By having the drones fly on a height of around 0,75 m of the floor, the drop height is not that high, but drones are still clearly visible.

Another issue with using drones at construction sites, would be that the blades of the drone could get damaged or tangled quite easily. For instance, many construction zones have large amounts of cables with different purposes hanging from the ceiling. By flying close to the floor, many of them will be avoided. To prevent the drone from getting stuck in a cable, damaging itself or the cable, it could be argued that the blades of the drone could get a cage surrounding it. The TU/e spin off "Blue Jay" has a perfect example. Its drone has a cage protecting both the blades of the drone as well as the users using the drone. If the drones were to be protected with a such a cage, it would be safer for both the construction workers and the drone itself.

Interaction

A downside of having the drones fly through the building instead of flying around the outside, is that it will have little space to maneuver in and encounter other drones, construction equipment and most importantly, construction workers. As humans, construction workers have to be kept safe under any circumstance. Therefore it is necessary for drones to get to their destination without getting in the way of construction workers. As construction sites can be filled with noise from heavy machinery, the noise produced by a drone would be drowned out. Construction workers would then be unable to hear the drone, and so a drone outside of their field of view could lead to dangerous situations. The two obvious solutions would be to either a) equip the drone with an alarm that is constantly ringing to alert construction workers, or b) let drones avoid construction workers all together. In this case it could be argued that the second solution is the best. If an alarm were to be attached to a drone, it would first of all drain battery power, of which the drones have a very limited amount. Secondly, humans are very good at filtering out irritating noises, which would mean that the construction workers actually wouldn't hear the alarm after a while. Avoiding the construction worker would have neither of these disadvantages. It would however be advisable to attach some type alarm to the drone, which could be rang if the drone where to get stuck between construction workers (and cannot find a way out) or if it has been damaged and dropped out of the air.

Another risk in using multiple drones, is that drones could potentially collide with each other. Not only would this have a great cost for the company operating the drones, it could also lead to dangerous situations for the construction workers. As it has already been advised at what height a drone should fly, it is ill advised to have drone fly at different heights and cross each other in that way. Flying next to each other is not always a possibility either, as many office buildings have narrow corridors. To circumvent this, it is advised to have drones fly through a narrow corridor only in one direction in a time. This would mean that multiple drones could fly in the same direction through a corridor, but not in the opposite direction. As path finding can reasonably optimized when using one way streets, the time lost by waiting for a drone to come through a corridor could be minimalized.

USE-case

In this paragraph a typical USE-case will be described. The setting is a construction site. This hypothetical case is based on feedback we got from the interviews we did with construction workers. During the first interview it became apparent that construction workers rarely lose their tools, for instance their hammer. The man mentioned that the project would, however, be useful for bringing supplies, for example a silicone kit. The current most popular solution, as reflected by the interview, is to do some other work until you have your next coffee break. In the next couple of lines the point of view from a construction workers will be pictured.

Imagine you are a construction worker, doing what construction workers do. You are at the 11th floor of the Atlas building with all your hammers, power tools and silicone kit. The task at hand is using your silicone kit to fill holes between two mounted objects. However, after an hour of using said silicone kit, it is nearly empty.

Now, you have a couple of options:

• Somebody needs to drop a few cans on the elevator
• You do something else in the time between now and your next break
• You call for drones

Since there is only one elevator, occupying it with only a couple of cans of silicone kit is not desired. So for the sake of argument, you choose to use to call it in.

You want a silicone kit, so you get your walkie-talkie and you ask the person downstairs to send a kit to the 11th floor central room. By the time you are done with your current kit, the drone with the next kit is already arrived and you can swiftly continue your work, while the drone goes back to its place in the storage. This way you avoided having to search for other work you have to do between now and your next break. Also, you can continue your workflow leading to no loss of efficiency at all.

Reality to model

To keep the goal of the project clear and the scope narrow enough to be attainable, it is necessary to make decisions on what to use in the model and what to leave out. Now that literary research has been done, it is possible to make educated assumptions and useful decision on the matter. As these decisions are vital to the project, showing them is of utmost importance.

Assumptions

• The goal of the project is to have drones deliver a parcel to a construction worker without any human intervention during its flight. This also requires the drone to return to the "distribution" point without any human intervention. We therefore assume that the drone will be able to fly from its starting point to the destination and back, carrying its cargo, without its battery dying.
• The drone will under no condition drop its cargo, but can only fail completely instead. Our model ignores this for the most part as the action one has to take is disable the broken drone and send another one.
• All floors in a building in which the drones are supposed to fly are at least 2,5m high..
• All requested objects can be carried by a single drone. The State of the Art mentions that it is actually possible to have multiple drones lift the same object, but this was abstracted from in this project.
• The objects that the drones are carrying do not affect their movement. Since the goal of this project is about moving obstacles through a building under construction while avoiding obstacles and humans, it is not necessary to simulate differences in movement due to payload. Furthermore, this is highly dependant on the actual drone itself in terms of hardware, which this project is not focused on.

Decisions

The deliverable is a simulation and the next step would be to actually make this software compatible with real drones that will fly through real construction zones. Before that step can be taken, it is necessary to restrict the freedom of the drones, such that a safe environment is created for both human and drone. Some of these restrictions can already be applied to the simulation, making them of utmost importance for this project to succeed. The following decisions were made to clearly define the boundaries of the drone.

• The first problem that comes to mind is whether the drone should primarily fly outside, or inside the building under construction. Both options seem equally unattractive. If drones were to fly at height, somewhere outside the building, it could come tumbling down to earth in case of failure, making it a lethal projectile. It is for good reason that tower crane operators are not allowed to use their crane unless the space surrounding the crane has been sufficiently cleared from other construction workers. Flying inside the building is not a great solution either, as the drones will often be in contact with the construction workers. As the drones have blades that turn rapidly, it is quite easy for a construction worker to get hurt. The final decision was made to have the drones fly inside the construction zone. This decision was made, because the danger of the blades can be mitigated by simply adding a protective shroud.
• Paths outside the building should not always be unavailable: sometimes there is just no other path possible and drones have to fly outside the building to reach their destination. It is however necessary to strongly discourage the drones from flying outside the construction zone. To obtain this, the cost for flying outside the building will be increased significantly. Then a path leaving the building will only ever be suggested when no other option exists. Furthermore the drone will only stay outside the building for as long as absolutely necessairy.
• It still has to be decided what a drone does while flying inside of a building. A good point to start is the height at which the drone is supposed to fly. Flying close to the ceiling is not a good idea, as it potentially hit a construction workers head or get tangled in cables hanging down from the ceiling. (see PRE2017 3 Group 17 - Interviews) Flying close to the ground is not great either, as it would be more difficult to see by construction workers and vice versa. Therefore a flying height somewhere between 0,75m and 1,00m seems to be a great solution. The drones will be clearly visible to construction workers, there is enough space to have objects hang from underneath the drone.
• How does a drone interact to a human? The goal is to deliver objects to construction workers, which implies the necessity of proper interaction guidelines for the drone and the worker. During its flights, drones will encounter workers walking or working on the construction. Since the drone is a 'tool' on the construction site, it is obvious that its place is after that of the worker. This means that the drones should always make way for the worker. The question remains however on how to implement this. For instance, the drone could either fly around a construction worker, wait for the construction worker to be done with his task or pass the drone, or avoid all integration by trying to find a new path without any human obstructions. Flying around the construction worker would potentially create dangerous situations, making this option not viable. Waiting for the worker could take a long time, and could drain the battery of the drone completely. Since it is not possible to detect how long a task will take, the drone will look for other ways to get to its destination in the meantime.
• How does the drone interact with the worker that ordered a delivery. To prevent conflict with the aforementioned decision to avoid contact between drone and worker, it is best for drones to drop the parcel and have the worker pick that up later, instead of having the worker detach the parcel manually. After the drone has taken off again, the worker that ordered the parcel could be given an notification that his parcel can be picked up at the nearby drop off point. This way direct contact between the drone and the worker is circumvented, making it the safer option.
• The drone is tasked with avoiding humans at all cost. This is done to prevent collisions which could either harm the human or damage the drone.
• There is still need for regulations that describe the interaction between drones. Nowadays, many buildings have corridors too narrow for drones to pass each other whilst flying at the same height. A solution would be for drones to fly over each other, or for a drone to wait at a point that is spacious enough for both to pass each other at the same height. Even though the first solution would be faster, it has already been decided that drones should fly at a set height, and having drones fly over each other with unknown cargo is not a good idea. So the decision was made to have drones pass each other at junctions (nodes). To prevent a chain collision, only two can pass each other at the same time. An exception to this is the Node with an ID of 0. This is the starting point of all the drones, or their 'storage' so to say, and it is assumed that these drones can all fit here.
• The abovementioned decision ties in with the decision to have only a single drone on a transition at the same time. If two drones were to fly in opposite directions, they would have to pass each other, which they can only do at nodes and not on transitions. Even though flying in the same direction should be possible, it is advisable for drones to keep some space between each other to reduce the chance of chain collisions. This way the operation is safer for both worker and drone.
• Besides being safe, it is necessary for all drones to actually reach their destination. To speed things up, the drones should have an internal map - model - of the actual environment that it updates dynamically. Then it sends this change to a central computer, which gathers all these updates, and distributes them back out, so that all drones have the same updated map. This also reduces the amount of computational power needed aboard a drone, making it less expensive and more agile.

Requirements

As mentioned in create simulation, a simulation will be created to demonstrate the capabilities of the program. However, if the program were to be made operable in the real world, it would have adhere to many regulations. Some of these regulations cannot really be shown in a simulation, but many can. Therefore the simulation has to adhere to the following requirements:

• As safety is our number one priority, it is important that the drones make no physical contact with any human, drone, or other obstacle. To be able to achieve this, it is required that the drones can detect every person, drone, obstacle, and wall.
• Another requirement is that the speed at which drones can fly through the building should be restricted. Even though flying fast is more convenient for delivery, it also likely introduces dangerous situations. A good middle ground seems to be 6-7 km/h. It is slightly quicker than walking, but can be easily caught up with if need be. Additionally, it is still possible to properly react to sudden changes of the environment and brake if need be.
• Drones should fly outside as little as possible, and it should be clear when a drone still decides to fly outside.
• To make the simulation realistic, it is required that construction workers walk around the building that is under construction.
• It should be possible for drones to detect and deal with dynamically adding and removing objects. These include but are limited to humans, non-permanent obstructing objects, and (permanent) walls.
• If this system were to be deployed in a real life situation, the drones would communicate with a central system. To closely resemble this interaction, it is necessary for the communication between the drone and parts of the simulation to be via the same pipeline, instead of drones directly asking access to the parts of the simulation. Otherwise, the model would be omniscient, which could not be the case in a real life situation.

Model

Now, the base requirements and assumptions are established. To make sure the model reflects these decisions, objects with different properties will be added. In The interface an example model can be found, where these objects can be found. All elements talked about in this section are part of the model, so they will disappear when the button 'm' is pressed as is explained in The interface.

Abstraction

Computers are really good at performing and storing many operations. Sadly, the real world is dynamic and therefore has infinite possibilities, which makes it practically impossible to exactly put it in a computer. It is therefore necessary to abstract from reality and create an environment, model, with which computers can work.

To greatly reduce the amount of computing power required, even with large buildings, the possible routes a drone can take will be restricted. The path a drone can take will be called Transitions or Edges, while junctions of paths will be called Nodes. The main advantage is quite clear. These Nodes and Edges can be stored in a computer efficiently as a graph. Since graphs are very popular in Information Technologies, a well-known algorithm will be adapted to suit the needs of the project. The result is a model that can find paths very quickly and efficiently.

Normal Nodes

The model works by using a graph created from a building plan. Graphs consist of nodes and edges. Normal nodes are just simply that, nodes between edges where drones can fly over. Drones can not pass each other in normal nodes, however if all requirements are met a normal node can be classified as a passing node. Nodes with only one incoming or outgoing edge are called leaf nodes, these nodes will typically only visited if it is the destination of a drone.

Elevating Nodes

A node connected to a node of a different level is called an elevating node. If a node is connected to a node on a higher level, then the former node will be an ascending node. Similarly, a node connected to a node on a lower level is a descending node. The former node is indicated in the UI with an triangle pointing 'up', while the latter is indicated by an triangle pointing 'down'. A node can also be both an ascending and descending node, then two triangles can be visible.

Passing Nodes

As mentioned before, passing nodes are special nodes in which drones have the opportunity to pass each other when coming from opposite directions. For the sake of reducing complexity of the project we chose to make every node a passing node, and can be found in the interface in the form of a black dot. In reality, however, these nodes have to be chosen more strategically. A few criteria and constraints that come to mind:

• Space, obviously, when a drone wants to pass another drone there needs to be room for the drones to pass each other. The amount of space needed is linearly dependent on the size of the drones. Naturally, the bigger the drones, the more space you need for them to pass each other.
• Leaf nodes cannot be passing nodes. Typically leaf nodes are in small rooms, thus having multiple drones stay in this room would be unwise with regard to safety. Besides that, the favored behaviour would be if drones would pass each other outside previously mentioned small rooms. This rule enforces that behaviour.
• Inactive place. Multiple drones will fly over these passing nodes, so it would greatly reduce performance of the model if these points where to be systematically blocked by construction workers having a lunch break for example. This could also be solved by the next bullet point.
• Enough passing nodes. Having more passing nodes leads to having more possible paths to the same goal. If a path is blocked by a obstacle, then having more alternative paths would deal with the possible congestion that could build up.

Normal Edges

Just like normal nodes, normal edges are simply edges that connect nodes. Drones cannot pass each other on edges, and all normal edges have the same level of preference. Normal edges are black lines between nodes in the interface.

Outside Edges

To reflect the decision that flying drones outside is dangerous, special edges called outside edges' are added. These edges behave mostly like 'normal edges' with the only difference being that these edges have a high 'cost'. The algorithm uses this to avoid going outside. The outside edges are red lines between nodes in the interface.

Blocked Edges

Previously, it was mentioned that edges could be blocked by obstacles. There are two different type of blocked edges: Temporarily and permanent blocked edges. The former is triggered by drones when they detect a human, since a human is bound to move the edge is expected to be occupied for a predetermined amount of time. This edge is found in UI as an edge that switches between different shades of green. The shade depends on the time passed. Every one thirds of the predetermined time has their own shade, and when all the time has passed the edge becomes black again, so it is checked by the next drone that has this edge in its optimal path.

Next, we have a permanent blocked edge. This edge is triggered by the drone when it detects a new wall or obstacles. Since walls are permanent, the model now knows that it there is no need to check this edge ever again, and just considers it unusable. In the UI this edge becomes blue.

Algorithm

Now that the building has been abstracted, it is finally possible for our program to find a path in a reasonable amount of time. Because we have abstracted the building to a set of nodes, several search algorithms could be applied, some better than others. We have opted to use the A* Algorithm. The great part about A* is that, when using an admissible heuristic, it finds the optimal path. Finding an heuristic for our building is quite easy. The Manhattan distance seems a good choice. Because all nodes have an x, y and floor position, this can be calculated quite easily. However, to prevent the drone from getting stuck at the required position but at the wrong floor, an multiplier for the floor difference will be used. This still makes the A* algorithm optimal, as the heuristic is still admissible.

Another decision that should be taken into account, is the fact that drones should evade flying outside the building. Therefore paths that are partially outside the building are weighted more heavily. They will therefore only be used if there is no other way for the drone to go, or all other paths will take too long for the drone to traverse.

Additional (Safety) Features

There are also two more features implemented into the algorithm that were not (strictly) mentioned in the requirements, but were thought to have a beneficial effect either way.

Sometimes it may happen that a drone cannot find a path to its destination (I.e. the destination is unreachable from the drone's current location). In such a case, the drone will stop at the nearest node (and will display an alarm icon in the simulation). However, if a drone were to be flying outside, stopping would be a very dangerous thing to do, since it would be hovering over a potentially high space. Therefore, the algorithm will send drones without a path to the nearest node inside the building, where such drone will stop (and display its alarm) instead. However, if there is no inside node that can be reached by the drone, it will follow its default alarm-behaviour: stopping at the nearest node, which in this case will be a node that's outside the building.

Furthermore, since flying outside is more dangerous the higher that outside area is, it should not be the case that higher outside areas have the same weight as lower outside areas. Therefore, a weight-scaling based on the edge's floor has been added to outside edges. In other words, a drone will avoid flying outside even more the higher the floor is. For instance, if a drone can only reach its destination by flying outside on either floor 3 or floor 4, it will do so on floor 3, since that floor is lower than floor 4.

The simulation

Now that all decisions have been made and requirements have been set, it is finally time to work on the final product. As we have decided not to work with real drones, it is necessary to create a medium through which we can show how the drones would operate and react with the environment if they were deployed in the real world. The chosen medium for this will be a simulation. This means however, that in addition to creating the program used to navigate the drones, it is also necessary to create an interface and simulation through which to interact with the program. Even though creating two separate programs would be more realistic, it would also be many times more difficult to implement. Therefore it was decided to put both in the same program, but restrict the communication between the simulated drones and the model, such that it could be decoupled quite easily.

Decoupling

The drones in the model and in the simulation are not directly connected. The "real position" of the drone is not known precisely at all times by the model, and is only updated once a drone hits a node to reflect this behaviour. As the model passes fly paths to the drones which they directly follow, the model does know all fly paths of all drones.

To prevent drones from flying over the same edge, the model 'locks' and 'unlocks' an edge in a similar fashion to how Mutexes work. When a drone wishes to enter an edge, it asks the model to enter the edge. If it is not allowed to do so by the model, the drone will wait. Once the drone is allowed to pass, the model locks the edge, preventing other drones from entering the same transition. Once this drone leaves the edge, the model unlocks the edge again, allowing other drones to move through it again.

The model receives an update when a drone detects an obstacle. This update includes whether the drone detected a permanent obstacle (E.g. wall) or a temporary one (E.g. scaffolding). The model then locks the respective edge containing this obstacle for a specific amount of time, based on the detected obstacle. This way, no drones will pass (or even try to pass) the respective edge.

The model can adjust the fly path of a drone at any time. For example, a drone's fly path can be adjusted when some paths are no longer locked and provide a faster route to the drone's destination.

The simulation

Now that all decisions have been made and requirements have been set, it is finally time to work on the final product. As we have decided not to work with real drones, it is necessary to create a medium through which we can show how the drones would operate and react with the environment if they were deployed in the real world. The chosen medium for this will be a simulation. This means however, that in addition to creating the program used to navigate the drones, it is also necessary to create an interface and simulation through which to interact with the program. Even though creating two separate programs would be more realistic, it would also be many times more difficult to implement. Therefore it was decided to put both in the same program, but restrict the communication between the simulated drones and the model, such that it could be decoupled quite easily.

In our simulation one can place workers, objects and walls to see how drones react to them. This is in addition to sending drones which would be available in an interface used for the algorithm if it were used in a stand-alone application. The simulation however does not take into account where the drones are and where they will be going when placing such walls, objects and workers. This was done because in reality workers will not know where drones are going either and drones should react to them going somewhere rather than the other way around. They can be placed on the same spot as where a drone is although this would not be something that happens in reality since such things do not just appear out of thin air.

Decoupling

The drones in the model and in the simulation are not directly connected. The "real position" of the drone is not known precisely at all times by the model, and is only updated once a drone hits a node to reflect this behaviour. As the model passes fly paths to the drones which they directly follow, the model does know all fly paths of all drones.

To prevent drones from flying over the same edge, the model 'locks' and 'unlocks' an edge in a similar fashion to how Mutexes work. When a drone wishes to enter an edge, it asks the model to enter the edge. If it is not allowed to do so by the model, the drone will wait. Once the drone is allowed to pass, the model locks the edge, preventing other drones from entering the same transition. Once this drone leaves the edge, the model unlocks the edge again, allowing other drones to move through it again.

The model receives an update when a drone detects an obstacle. This update includes whether the drone detected a permanent obstacle (E.g. wall) or a temporary one (E.g. scaffolding). The model then locks the respective edge containing this obstacle for a specific amount of time, based on the detected obstacle. This way, no drones will pass (or even try to pass) the respective edge.

The model can adjust the fly path of a drone at any time. For example, a drone's fly path can be adjusted when some paths are no longer locked and provide a faster route to the drone's destination.

The interface

Here a screenshot of the main interface is shown together with an index indicating the meaning of what can be seen. Below we will explain more about this interface and interactions possible in it.

Interaction

Mouse Buttons

In Model, most of the elements from the model where explained. So for the full explanation it is advised to also read that section. On top six buttons are visible, which are also available in the menu you get when right-clicking on the model:

• "Send drone": A drone will be deployed after selecting a node with the Left Mouse Button. (When using the option in the right-click menu, the drone will be deployed to the location from which the menu was opened instead)
• "Place Worker" places a Construction Worker. Workers act like similar to obstacles, but unlike those they have a fixed size and are able to move.
• "Draw Wall" requires two button presses afterwards; the starting point of the wall and the endpoint of the wall. (When using the respective option in the right-click menu, only the endpoint needs to be selected). Walls can only span a single floor at the same time. If drawing a wall would violate this principle, the action will be cancelled. Drones cannot fly through walls, and will mark edges passing those as 'Permanently blocked'. While drawing a Wall, a Ghost Image of it appears to indicate where the wall will be placed. If attempting to move the endpoint to an invalid area (E.g. another floor), the ghost image will snap to the latest valid endpoint to indicate this.
• "Draw Obstacle" places an obstacle. Placing is done the same as placing a wall, and follows the same rules too. Drones cannot pass obstacles, and will mark edges passing those as "temporarily blocked". This temporary block will be removed again given some time. This time will be longer the more often this edge has been blocked.
• "Move Worker" moves a worker. A worker needs to be selected first, and a destination can be picked afterwards. (When using the option in the right-click menu, only a destination needs to be picked.) A worker cannot walk through walls, and is as such able to navigate complex mazes!
• "Remove" removes all temporary obstacles at a given location, such as workers. Walls cannot be removed, as those are permanent.
• Scrolling up will shift your view a floor up (if possible), and scrolling down will shift the view a floor down (if possible).
• The status bar is empty most of the time, but when the simulation is paused etc. the program will inform the user through this box. It also informs the user what to select when using any of the above options.

Keyboard Buttons

• "m" toggles the model, when the model is off, the elements described in Model will disappear as can be seen in the second image below.
• "r" restarts the simulation. Since walls are permanent, this is the only way to remove them without stopping the simulation.
• "escape" cancels any action that was active, so for instance if you did not press a second time when placing a wall the action can be canceled by pressing this button.
• "p" pauzes the simulation. Time will freeze.
• "1", ..., "6" correspond with the mouse buttons
• "->" will shift the top down view one to the right
• "<-" will shift the top down view one to the left

Display of the Floors

A side-view of the building can be viewed at the left of the screen in the simulation. It gives a clear overview of on which floors the drones, obstacles, and detected workers are.

Furthermore, since the UI only has place for the top-down view of three floors, between which can be scrolled, it should be clear which floors are currently visible. This is made clear by the floor numbers under each top-down view, as well as by highlighting (with a darker shade of grey) which floors are visible on the screen in the side-view.

Drones

Drones are drawn as quadcopters in this simulation and have a flying animation. Each drone also has a green circle around it, which is the detection range. A drone is not omniscient according to the assumptions, so when a object is in the way the drone will detect it only if it is in this circle. If the model layer is on, like the first image below, the program shows a semi-transparent quadcopter in the place where the model got the drones last location.

If the model no longer can find a path for a drone, this drone will be marked with an alert sign as can be seen in the screenshot above. This is to indicate to the person controlling the simulation that the model is unable guide that drone to its destination.

First three floors of the interface.

First floor up until the 3rd floor; Model disabled.

Who does what?

Monday 5th of March 2018:

• David Tuin: Working on the model
• Menno Hofste: Thinking of USE cases, and updating Wiki.
• Rene Nijhuis: Updating SOTA with information required by our project.
• Erik Takke: Creating interview and interviewing construction workers.
• Eric Arts: Creating interview and interviewing construction workers.

Thursday 8th of March 2018:

• David Tuin: Working on the model
• Menno Hofste: Creating test cases
• René Nijhuis: Writing input parser
• Erik Takke: Creating CSV files from test cases to be parsed
• Eric Arts: Creating test cases and creating CSV files

Monday 12th of March 2018:

Our general planning for working on the model is to split the group up into 4 categories and let everyone rotate. The categories are:

• Model/Algorithm
• Simulation
• GUI
• Creating the final test case (building)

Other things that need to happen should be done by every member and are:

• Updating the wiki
• Preparing for the meetings

In the penultimate week of this project (the week before the final presentation; 22nd of March, 2018), many of these categories were already finished, after which the following planning took effect:

• David Tuin: Finish up the simulation; mainly bug fixing
• Menno Hofste: Update the wiki regarding the GUI
• Rene Nijhuis: Finish up the simulation; mainly bug fixing
• Erik Takke: Prepare the final presentation
• Eric Arts: Prepare the final presentation

In the last week of the project (29th of March, 2018), all team members are expected to update this wiki. This may include adding sections, re-writing sections, or making suggestions of missing or wrong information on the wiki.

Test Cases of the Model

To keep this page clutter free, the following page has been created: PRE2017 3 Group 17 Test Cases. It contains (simple) test-cases that were used to test the model's path calculation. Some tests also required us to think of specific 'trade-offs' or 'interactions' that needed to be made.

Discussion / Reality Check

In this last part of the wiki, we will shortly reflect on what we have made. If it is relevant for the users, and what would need to be changed to make the project more applicable in real life.

A big drawback of the program is, that it requires a construction map with all the nodes filled in. In the State of the Art, a few algorithms are mentioned that can do this, but even then until this algorithm is created our model relies on manual input of the graph, which can only be constructed with the right amount of knowledge of the workings of the program. Another problem with the project in general has to do with the fact that our model powers a simulation rather than a real world scenario. This results in some details not being implemented in the model. Following are some examples of these details,

• Drones are added with the start of the program, and cannot be added while the program is running
• Physical drone failure is not dealt with
• Loss of communication would result in the model waiting endlessly for the drone to get into place

Besides these drawbacks we also have the limitations of the simulation that play a role,

• Drones can only fly over edges. Even if the drone could easily fly around a human without endangering him/her, it will try to choose another path. This can be solved by choosing the edges optimally.
• Pass over Passing Nodes. In reality drones could also pass each other over edges if there is enough room. This can also be partially solved by choosing two edges that are a drones length apart. It must be noted that this would only be a workaround, but not a viable permanent solution as opposed to the solution above.
• Trajectories and flight paths are not influenced by the object the drone is carrying, while the flight time is handled by the model, if the drone carries something very large, and cannot make use of certain nodes, the model cannot give any more information.

And there is also the functions which we assume drones are capable of which they at this moment can not do:

• Live and perfect recognition of objects, humans and walls. And in real life more complicated cases like cables hanging from the ceiling and windows with clear glass.
• Being able to track its location in a building with great precision.
• Flying with objects while staying stable in the air and not hitting anything with the drone or the object being carried.

Coaching Questions

Coaching Questions Group 17