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 final deliverables will be a working simulation that shows drones flying to their respective destinations. The software will contain the above mentioned features. Additionally, this wiki will be delivered, containing all information used to create the simulation.

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 BlueJay. 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 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.

Find path

The system will be equipped with a layout of the construction zone. From this layout a graph can be created, which will be used to find the optimal path the drone will use to travel to the destination. Since this graph will stretch over a 3D building this will be quite the challenge to create.

Two way paths

Especially in office buildings, corridors will be quite narrow. This could potentially 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 spacious intersection will appear in the model with the use of special 'passing nodes'.

Evade objects and agents

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

The model, as previously mentioned, also incorporates the use of multiple drones for different tasks at the same time. This means that there can be more than one drone in the model at a given moment. How this is dealt with can be read in passing nodes. Furthermore, the model incorporates obstacles. These obstacles can either be blocks, balls, humans or walls. The model works under the assumption that the drone itself can detect the obstacle, while the model makes 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.

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.

Users and what do they require?

• Construction companies
  • The drones will have to be able to have sufficient lifting power.
  • The drones will have to operate by themselves
  • The drones will have to be able to detect and avoid all living agents.
  • The system has to adhere to safety regulations.

Approach & Milestones

1. Have concrete idea.
2. Have a basic model. This model will show the basic interface and will not be interactive and only features one drone.
3. Add interactivity to the simulation to test the dynamic components.
4. Add walking humans to the simulation and ways to get around them in the model.
5. Upgrade the simulation to multiple drones.
6. Upgrade the model to use one way locks or other optimizations.

Deliverables

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. This should give a clear view of what the developed software is capable of.

The users

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.

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 one 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.

Decisions

Even though our deliverable is a simulation, a next step would be to actually implement this software in 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 is because it is more difficult to safely bring a drone down from high up, than it is to cover all moving parts of a drone in such a way that it is really difficult for it to hurt a construction worker.
• Even though that is decided that the drones should primarily fly inside the construction zone, that does not mean that paths outside the building should 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 be suggested when no other option exists and the drone stay outside the building for as short as possible.
• Now that the drone flies inside the building, it still has to be decided what it is allowed to do there. 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. Flying close to the ground is not great either, as it would be more difficult to see by construction workers and because small objects lying on the ground will always form an obstruction. It therefore seems that 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 and small objects can be flown over.
• Another decision that had to be made, was how a drone would interact with a human. It is ofcourse the goal to deliver objects to construction workers, which would suggest 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. Because the drone is a helping hand 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 it an non-viable option. Waiting for the worker could take a long time, which will drain the battery of the drone, e.g. a worker is performing multiple drillings in a narrow corridor. It is not possible for the drone to see how long this task still takes, and the potential for communication between the drone and worker is minimal. This leaves only one option: to avoid workers at all cost and try to find a new path if one is blocked by a worker. A similar thought process can be used to deduct that trying to find a new path when encountering a stationary obstruction is also the best solution.
• Another decision that has to be made, is how the drone is to 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. This would require for the drone to land, detach its parcel and take off, all by itself. 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 all the safer.
• Even though the drone is tasked with avoiding humans at all cost, it is unrealistic to say that no situations will occur in which the drones will come in contact with a construction worker. If this contact were to cause a collision, it is a must to prevent either party from getting hurt. Therefore it is of utmost importance for all moving objects on the drone to be properly closed of. A nice solution would be to create a cage which encloses the blades of the drone. An example of such a cage can be found in the BlueJay project. The cage prevents large objects from getting hit by the propellor blades of the drone, yet still allows the drone to fly freely. Additionally, the cargo carried by the drone may also have sharp edges, e.g. a hammer of screwdriver. It is therefore necessary for the cargo to be in a closed of container, when it has sharp corners or edges.
• Now that the interaction between workers and drones is clearly set, there is still the 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. Flying over each other would require for either drone to either get too close to the floor or to the ceiling. As the second option is viable, 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 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. That way it is less likely for drones to have chain collisions. This way the operation is safer for both worker and drone.
• Besides being safe, it is of course needed 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. This way the drone can evade paths that were blocked by construction workers or obstruction a couple of minutes ago, and try to take paths that have a higher likelihood of being free. As different drones encounter different obstructions in different parts of the building, it is useful to gather all that data and combine it in a single comprehensive model that can by all drones to navigate the construction zone. To achieve this, the decision was made to have a central nervous system that will tell the drones where to and where not to fly. Another advantage that comes with this, is that the drones do not have to massive computing power on board to process all that data. This keeps the drones lighter, which makes them in turn 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.

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.

Safety features

The model also has some additional safety features such as:

• Drones which are stuck on outside nodes or transition are send to some nearby inside location.
• The drone will only fly on outside nodes when it is the only or at least a substantially shorter distance. This also scales with height so higher up it will take the outside even less.

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.

Abstraction

Computers are really good at performing and storing many operations. Sadly, the real world has infinite possibilities, which makes it practically impossible to put 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.

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, A* 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.

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

Index

A screenshot has been included as a reference on the right.

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, 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.

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.

References

Coaching Questions Group 17