Senior Design Project Spring 2018

Drones Delivering Items: A Drone Simulation How To

Matthew Phillips

Warning! This page is only a draft! There will likely be changes made to this page in the near future!




Introduction

Delivering packages one by one, walking to the front door and then back to the delivery truck, is inefficient.

One solution to this would be to use multiple drones, with each drone carrying a package to its destination. When that drone reaches the destination of that specific package, the drone will put the package down on the ground, and then return to the delivery truck to deliver the next package.


Before actually testing all of this in the field, a simulation has to be made before using any physical resources for such an project.

The simulation would need to use both A* and Dijkstra's pathfinding algorithms for the pathfinding of the drones and trucks, with both algorithms being timed for each drone delivering a package. The simulation would also need for the drones to start from the same position as the truck each drone is assigned to.


Of course, there are multiple reasons to create a simulation before attempting such a project.

One of those reasons would be that, to know whether this would be more efficient, a simulation would have to be made, before any physical materials were to be assigned for such a project. Also, if drones are used, the drones would have only a certain range that they could operate while still keeping in contact with the truck. Plus, the truck driver would need a means to input the destinations for each package.


Approach

The program already had Dijkstra’s algorithm for the drone’s pathfinding.

Because of this, adding in A* was like adding a new variable, the heuristic function, to an already existing equation. The main part for doing this was to bring the heuristic formula into the program, but there was also making sure that it also only looked at nodes that got closer to the goal node. The heuristic is a function that ranks every alternative step in searching algorithms at each branch. The step the function takes is always the step closest to the solution or goal node. Because of this, A* is what some may call biased, but it always takes the optimal path. Below are examples of how the A* algorithm works.



function A*(start, goal):

// The set of nodes already evaluated

closedSet := {}; // The set of currently discovered nodes that are not evaluated yet. Initially, only the start node is known.

openSet := {start}; // For each node, which node it can most efficiently be reached from.

// If a node can be reached from many nodes, cameFrom will eventually contain the most efficient previous step.

cameFrom := an empty map;

// For each node, the cost of getting from the start node to that node.

gScore := map with default value of Infinity; // The cost of going from start to start is zero.

gScore[start] := 0 // For each node, the total cost of getting from the start node to the goal by passing by that node. That value is partly known, partly heuristic.

fScore := map with default value of Infinity; // For the first node, that value is completely heuristic.

fScore[start] := heuristic_cost_estimate(start, goal);

while (openSet is not empty){

current := the node in openSet having the lowest fScore[] value

if (current = goal){

return reconstruct_path(cameFrom, current) openSet.Remove(current) closedSet.Add(current)

for each neighbor of current {

if (neighbor in closedSet) continue; // Ignore the neighbor which is already evaluated.

if (neighbor not in openSet) // Discover a new node

openSet.Add(neighbor) // Distance from start to a neighbor. the "dist_between" function may vary as per solution requirements.

tentative_gScore := gScore[current] + dist_between(current, neighbor)

if tentative_gScore >= gScore[neighbor] continue // This is not a better path. This path is the best until now. Record it!

cameFrom[neighbor] := current

gScore[neighbor] := tentative_gScore fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal) ;

return failure;


function reconstruct_path(cameFrom, current)

total_path := [current];

while (current in cameFrom.Keys)

current := cameFrom[current] total_path.append(current);

return total_path

}


Example of A*

The equation for the A* pathfinding function boils down to f(v) = h(v) + g(v), where v represents the vertex.

G(v) is the current path cost to the current vertex, while h(v) is the heuristic estimate of the approximate distance left until reaching the goal. G(v) is also the same cost function as the one Dijkstra’s Algorithm uses to find the closest neighboring node. When g(v) and h(v) are used in tandem, the result is that the algorithm will search through only half of the neighboring nodes, and from those nodes only, pick the path that both has the shortest path and leave the least remaining distance to the destination (in other words, the optimal path). An example of Dijkstra’s Algorithm is given below.


function Dijkstra(Graph, source):


create vertex set Q


for each vertex v in Graph{ // Initialization

dist[v] ← INFINITY // Unknown distance from source to v

prev[v] ← UNDEFINED // Previous node in optimal path from source

add v to Q // All nodes initially in Q (unvisited nodes)


dist[source] ← 0 // Distance from source to source


while (Q is not empty){

u ← vertex in Q with min dist[u] // Node with the least distance

// will be selected first

remove u from Q

}

for each neighbor v of u:{ // where v is still in Q.

alt ← dist[u] + length(u, v)

if (alt < dist[v]){ // A shorter path to v has been found

dist[v] ← alt

prev[v] ← u

}

}


return dist[], prev[]

}


Example of Dijkstra's Algorithm

Before making the path to the goal, the goal had to be redefined.

The goals needed to be changed so that the simulation would only create paths to the destinations for the packages. To do this, a new .txt file was created, from which the program was intended to read from it, the destinations of the packages, how many trucks would be in the simulation, and the number of drones per truck.


After that, work started on the initialization.

For the simulation to be as accurate as possible to real life, each of the drones had to have their initial positions set to be the same as the position of one of the trucks, and the packages had to been given their own graphics. However, since I had no prior experience with graphics, the idea of creating the packages was put to the side. Instead, they were only in the code as a variable that would decrement (decrease) by one, every time one of the drones with a package reached its destination.


For changing the initial position of the drones, each of the drones had to be assigned to a specific truck.

To do this, 2D array was used, with variables I (the number of trucks) and j (the number of drones per truck). Because this was a research project, parameters had to be limited. Because of these parameters, the number of drones per truck had to be kept down to two, with only three trucks (resulting in a total of six drones). By using an array for assigning the drones to trucks, it was possible to also reference the location of each drone to that of its own truck (or source truck). Because of this, a loop could be run, comparing their locations with each other. If they were the same, then the program could say that that Drone [I] [j] (or Drone J of Truck I, like Truck 1’s Drone # 2) was inactive or grabbing the next package to deliver. If their locations were different, then it would run a second loop, comparing the locations of the drones and the destinations for the packages. If it was the same as the destination, the simulation would output to the command prompt that the package [k] had been delivered, decrement the number of packages left, and have the drone return to the truck to look for another package to deliver, if any were available. When all packages had been delivered, all of the drones would return to their respective trucks, and the simulation would pause itself.


Within the time frame of this project, there were some parts that had to be prioritized over others.

While the 2D array for the trucks and drones was created, importing the package destinations, number of drones, and number of trucks, from the .txt file to the program had to wait. Due to this, the number of trucks had to be hard coded in, and the number of drones (numAgents3D) were set to be equal to the number of trucks, multiplied by two. Since the program would not take the imported destinations, the drones and trucks kept going to randomly set destinations. Due to this, the destinations had to be hard coded as well, into the function that was supposed to read them. Also, since the enum Availability (available, enroute, delivered) refused to work with the Vector3D, a String was used instead, that would update which packages had already been delivered.


Conclusion

When all of the needed work is complete, the limits of the program will be tested and the code will be debugged for any errors

in the code or either of the pathfinding algorithms (A* and Dijkstra’s), and double check on the heuristic function to make sure it functioned correctly. After that, the code for the initialization of the simulation would be double checked for any areas that could be improved upon, such as the pairing between drones and trucks, and their initial starting positions. Then, the parts of the code that had not been finished would be worked on, such as importing the destinations from an .txt file. Finally, after all of this is finished, work would begin on turning the simulation into a program that a drone could then follow, allowing it to drop off packages at their destination, and would be more efficient than walking to each door to deliver each package.




Video of the simulation: