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, often the construction has advanced to the point that cranes can no longer reach said spot, creating a problem. This problem is usually solved by using all different types of transportation to get the object to its spot. 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 drones. As small, fast and really maneuverable vehicles, they seem to be a good solution to this problem. To make this a reality, it is our plan to develop a piece of software that can guide the drones through or around buildings and have them deliver the object. 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. All to have the drone reach its destination.

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. (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 PRE2017 3 Group 17 - 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 PRE2017 3 Group 17 - Interviews.

It is however useful to summarize the findings of the performed research. First of all, drones are already used at construction zones, but rather 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. 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 rough layout of what the construction zone looks like. Based on this rough layout, the system has to be able to find a path that will bring the drone from its starting point to its destination. As the path does not just have to be a 2D but rather a 3D route, 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.

Evade objects and agents

However, just like in every construction zone, obstacles (such as scaffolding) will be moved constantly, making for a dynamic environment. Therefore it will be necessary for the algorithm to adjust its path on the fly, evade objects/obstacles and still find a path to its destination. Additionally, if the idea were to catch on, it would be possible form multiple drones to simultaneously bring objects to different destinations. To prevent the drones from flying into each other, they will have to be able to detect and evade each other. The same can be said for humans: construction workers could potentially be walking all over the place. To prevent them from getting hit and be injured, the drones will have to be able to detect them and stop/evade them.

Create simulation

As we do not find it responsible to use this software in real drones flying through construction sites, we would not be able to show the final product. As this would render this project useless, we will also create a simulation 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, 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 example building is yet to be made available on this wiki, as it is currently WIP.
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.
• (Remove a transition)

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 finds 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 are, it or its load, both with significant weight, would come tumbling down. It could potentially harm one or more construction workers if it were to fall on top of them. It is therefore necessary that flying them 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 drones have 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 a drone outside of their field of view, which 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 use the new app

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 the app.

In the app you can see the inventory of the construction site storage, neatly organised. From here you select the silicone kit, the app says it is available through drone delivery. You choose an appropriate time you want it delivered, in this case ASAP. 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.

Decisions and Assumptions

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.
• Only a single drone may be on a transition at the same time
• 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.

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.

Requirements

As just creating a program will not make you or any of us exiting, a simulation will be created in which the program can be shown off. 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 it is the final goal to have these drones operate in the real world, it should operate safely for humans. %% TODO: maak dit af!. It is therefore necessary for every drone to detect all objects, walls and humans, without fail.
• simlation does not directly pass information to the program
• There are Construction Workers walking around in the building, with whom the drones have to deal with
• 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.
• Drones are not perfect:
  • Speed is variable
  • Detection might take some time
  • They can fail

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

testTExt!

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

Model

PRE2017 3 Group 17 Test Cases

References

Coaching Questions Group 17