What you need to:

1) Code for the whole project, and some pictures and explanation of how this code running and the demo of the program. Explanation of how you could use the code. (Use he latest vision of Spyder(Anaconda) for python code writing)

2) A 2-page report for the theory and method used for the A* algorithm and dynamic environment.

Important parts.

1) A* routing algorithm is the basic principle of what we use for this project.

2) The drone in the grid should be able to learn the environment in a 3x3 grid, which means the environment is a real-time environment, there is the definition for the real-time environment in the previous file under Aims. (Such as traffic lights, other cars and how the drone decided to take the other route or stick the same route before.)

3) what I want for the variables to be optimized is TIME consumed to travel from A to B.

Tasks from last week:

- Stakeholders, companies. Who are they? Heathrow auto-taxis, city councils, Google, etc.

- Research what's already been done, search algorithms

- How to design the environments? Defining children states and obstacles?

- Work on some example codes we can share. Python better for machine learning. Best to stick with one language to avoid confusion. (pygame currently unsupported by Py3.6, older versions work)

Aims:

- Planning a route (A to B) where the drone has knowledge of the static environment. In real time, no static or dynamic obstacles. Investigate how to weight cost vs heuristic. Assuming complete knowledge of the environment with no additional obstacles.

- Next define the drones knowledge of the environment separately to the real-time environment. Drone will still have knowledge of the empty environment (walls, buildings, shelves etc.). In addition, real-time environment will include randomly placed obstacles that the drone will not be aware of initially. As the drone explores, it will be able to update the knowledge of its local surroundings within its field of vision (see methods), in order to reroute itself if a path is blocked.

- Incorporate a measure of risk / reward in to the algorithm (revisit how to weight cost, heuristic and risk), possibly measuring risk based on number of surrounding obstacles.

- Add dynamically moving obstacles (cars, people, etc.). Assume they move at the same rate as the drone.

- Add time-variant obstacles, e.g. traffic lights / junctions that are (not) passable at certain times.

- Add option for multiple destinations (maybe the drone has to make deliveries at multiple locations)???

Questions:

- Variables to optimise: energy(distance, time?) consumed

- Parameters to tune: maximum waiting time, weighting of cost vs heuristic vs risk.

- Inputs for drone: Complete layout of empty environment, number of randomly placed static obstacles(?), number of randomly placed dynamic obstacles(?).

- Is it worth being able to distinguish between static and moving obstacles (e.g. a person vs a crate / fallen tree) as opposed to treating all unexpected obstacles equally????? Investigate how much better (/worse) algorithm performs

Methods to be used:

- To analyse the performance of a drone, first run the simulation normally (with the drone only having some knowledge of its environment, not including the locations of randomly placed obstacles), then for comparison, rerun simulation with the drone being given complete knowledge of all obstacles (including randomly placed ones). In theory, if the drone is provided with perfect knowledge from the beginning it will be able to find the (cost of) the best route. The actual route the drone finds can then be compared to this ‘perfect knowledge route' in order to measure how optimal it is.

- In order to navigate through the environment, the drone will be able to move horizontally, vertically or diagonally by one grid square per time step. The cost of moving horizontally or vertically will be 1, whereas the cost of moving diagonally will be √2. Cost will relate to energy expenditure? The drone will only be able to move diagonally if it could also reach the same grid square via a combination of one horizontal and one vertical movement that do not cross any obstacles (this prevents the drone from being able to ‘hop' over diagonal walls).

- When including dynamic obstacles such as staff, vehicles, maybe other drones etc., the drone will also have the ability to wait in its current state for a time step **will need to make an assumption of the energy expended whilst waiting**.

- Construct heuristic from euclidean distance between a given grid square and the destination grid square. Obstacles will have a heuristic equal to twice the number of squares on the grid (an arbitrarily large value)

- In order to update the drones knowledge of its local surroundings, an algorithm will scan up to 3 **may be changed** grid squares to the left, right, up, and down and up to 2 **may be changed** grid squares in all diagonal directions. Grid squares in between these trajectories will also be considered - drone will essentially have a diamond-shaped field of vision. The drones knowledge of any grid squares that are not occupied by or ‘behind' obstacles will be updated with the real-time information about the environment on each time step.

Attachment:- Questions.zip