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. To show the progression of our project, this wiki has been brought to life. On this wiki page you can read all about our project: the choices that have been made, the progression of development and much more. Enjoy!

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 abovementioned 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 eachother in corridors. (achieved on 22-03)
7. Implement features to dynamically adjust the models environment. (achieved on 22-03)
8. Finalize project.
   
   

The final deliverables will be a working simulation that shows drones flying to their respective destinations. The software will contain the abovemetioned 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. Eventhough 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 spaceous intersection. This spaceous 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 show-cased. 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.
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.
• Make a specific drone fail.

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 situtations 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. Eventhough 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 advisible to attach some type alarm to the drone, which could be rang if the drone were 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 diffent 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 apperant 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 starts te become 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 4th floor's 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 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. This means a new drone has to be send with the same cargo.
• All floors in a building in which the drones are supposed to fly are at least 2,5m high. Obstacles are however capable of lowering that number from place to place.
• 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

As our deliverable is a simulation, it is necessary to put boundaries on which parts of reality will and which will not be taken into account in the model.

• We deem it dangerous for a drone to fly outside the building. If a drone were to drop its cargo or have failure at height, the falling object could become a deadly projectile. To prevent this from occuring, the following has been decided:
  • The path cost used by the search algorithm will be created in such a way that flying outside the building is strongly discouraged.
  • Whilst flying inside the building, the drone will fly fairly close to the ground, at about 0,75m height. This way it would be seemingly impossible to drop cargo on the head of a construction worker.
• If a drone were to encounter a human or other obstruction during its flight, it will tell the system to block that path temporarily and find a new path to its destination. This way the drone completely avoids humans.
• Eventhough the drone is tasked with avoiding humans at all cost, situations will occur in which the drones will come in contact with a construction worker. To prevent either party from getting hurt, it is necessary for all moving objects on the drone to be properly closed of. A nice example would be the cage used in the BlueJay project. The cage prevents large objects from getting hit by the propellor blades of the drone.
• Drones can pass each other at junctions (nodes), but 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.
• Only a single drone may be on a transition at the same time

Requirements

As mentioned in Create simulation a simulation of the program will be used to demonstrate its capabilities. 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 program has to adhere to the following requirements:

• Drones detect every person, object and wall.
  • As safety is our number one priority, it is important that the drones detect human without fail, so the model can react. If this were not the case, the model would have no way of reacting on the obstacles.
• simlation does not directly pass information to the program
  • Since it is a simulation, it is a requirement that input from the simulation to the model is limited, so as to prevent omniscience.
• There are Construction Workers walking around in the building
• Walls can be added so the path-finding has to change
• No-fly zones (I.e. obstacles) can be added dynamically, for example if there are Construction Workers working at a specific location or if there are cables hanging from the ceiling.

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 dissapear 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 annode 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 lineairly 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.

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. Eventhough creating two seperate 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 discrete operations. Sadly, the world as we know it is continuous, which makes it quite difficult to put in a computer. It is therefore necessary to abstract from reality and create an environment which computers can work with.

We have therefore abstracted a building into junctions and lines between junctions. These will be called Nodes and Transitions respectively, from here on out. These nodes and transitions can be saved quite easily and, more importantly, can be searched through very quickly.

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

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

Write something about the following:

• decoupling between realDrone and modelDrone
  • how the model does not always know exactly where the drone is
  • drone just gets coordinates to fly to
  • reports back if there is an obstacle
  • model recalcs path, lets drone know.

The interface

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 will also be available in the menu you get when you right-click on the model.

• When pressing "Send drone" and afterwards pressing near a node will result in a drone being deployed towards that node.
• "Place Worker" places a worker. This worker has a black body and a yellow hat an can be seen in the ground floor of the first image below.
• "Draw Wall" requires two button presses afterwards, the starting point of the wall and the endpoint of the wall. This wall can only be drawn on one floor at the same time.
• "Draw Obstacle" is similar to draw wall, the difference is that the first click will be the left upper angle, and the second click will be the right lower angle.
• "Move Worker" makes you select a worker and a destination. This worker is also able to navigate complex mazes!
• "Remove" is pretty self-explenatory, it can remove all obstacles, except for walls, because they are permanent.
• Scrolling up will shift your view a floor up, vice versa.
• The status bar is empty most of the time, but when the simulation is pauzed etc. the program will inform the user through this box.

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

Building

On the left hand side the side-view of the building can be observed to give a make it easier to follow where drones are moving towards. Furthermore, the UI has, in this case, only place for three top down views. These three views are made darker on the left hand side to make clear which three floors are being viewed. To the side if this side-view are the three floor maps can be found with their floor number written below it.

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-transparant quadcopter in the place where the model got the drones last location.

First three floors of the interface.

Second floor and onward, 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
• Rene 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 test cases (buildings)

Other things that need to happen are:

• Updating the wiki
• Preparing for the meetings

TODO: update from "notulen"

Model

PRE2017 3 Group 17 Test Cases

References

Coaching Questions Group 17