Click here to watch the presentation.

Path planning has been an useful method consists of motion planning in different aspects, like self-driving vehicles, humanoid robots, aviation engineering, etc.. In aviation engineering, path planning is one of the important steps before the aircraft starts the journey.

To begin with, the algorithms of path planning is used to compute a continuous path that connecting the start point and the goal point, avoiding collision with obstacles. The path planning algorithms generate a geometric path, passing through free space, as known as C free, from initial point to final point. Since path planning is a procedure that is used to figure out what the status of the area around the starting point and the final point, it is needed to calculate what is the best solution under certain restricts, in order to find out the best route that can avoid obstacles, also the shortest route that can use the least time.

Moreover, without path planning, it is even impossible for us to plan a path. Since without path planning, we could not figure out what is the exact topography, and also other situations that can affect the motion going on the path. It will make the whole motion become way more complicate to go on the path and also increase the percentage of accidents happen. Therefore path planning plays an important role in the every aspects that consist of motion, including flight planning.

Flight path is dependent on the model of the aircraft, including the acoustic characteristics, engine power of the aircraft. Flight path can be different due to the wide range of variables of the aircraft. Therefore, it is important to calculate all the major and minor factors of the aircraft that can affect the flight paths, in order to make a shortest flight path that can have the most cost and time reduction for each particular aircraft.

Flight plans are documents filed by a pilot or flight dispatcher with the local Air Navigation Service Provider (e.g. the FAA in the United States) prior to departure which indicate the plane's planned route or flight path. Flight plan format is specified in ICAO Doc 4444. They generally include basic information such as departure and arrival points, estimated time en route, alternate airports in case of bad weather, type of flight (whether instrument flight rules [IFR] or visual flight rules [VFR]), the pilot's information, number of people on board and information about the aircraft itself.

Flight path can be thought of as three-dimensional highways for aircraft. In most land areas of the world, aircraft are required to fly airways between the departure and destination airports. The rules governing airway routing cover altitude, airspeed, and requirements for entering and leaving the airway (see SIDs and STARs).

SIDs and STARs are procedures and checkpoints used to enter and leave the airway system by aircraft operating on IFR flight plans. There is a defined transition point at which an airway and a SID or STAR intersect. A SID (Standard Instrument Departure), defines a pathway out of an airport and onto the airway structure. A SID is sometimes called a Departure Procedure (DP). SIDs are unique to the associated airport. A STAR(Standard Terminal Arrival Route), ('Standard Instrument Arrival' in the UK) defines a pathway into an airport from the airway structure. STARs can be associated with more than one arrival airport, which can occur when two or more airports are in proximity (e.g., San Francisco and San Jose).

The flight paths are corresponding with several aspects: First, in the airline prospective, every commercial airline flight start begins with a flight plan. A well-designed flight path can bring great benefits to the airline, including flight safety and economy. For flight safety, an operational flight plan is required to ensure an airplane meets all of the operational regulations for a specific flight, to give the flight crew information to help them conduct the flight safely, and to coordinate with air traffic control (ATC). For economy, a well-designed flight plan includes the route the crew will fly and specifies altitudes and speeds. It also provides calculations for how much fuel the airplane will use and the additional fuel it will need to carry to meet various requirements for safety. By varying the route (i.e., ground track), altitudes, speeds, and amount of departure fuel, an effective flight plan can reduce fuel costs, time-based costs, overflight costs, and lost revenue from payload that can't be carried, that it leading to saving money for the airline.

Next, in the ATC prospective, path planning is crucial in maintaining efficient use of airspace with balance public interest as aircraft operations produces noise to the surrounding community. Therefore, when constructing flight path (SID/STAR) in AIP noise mitigations measures are considered following ICAO guidelines. Take Hong Kong as example, aircraft operations between 11pm to 7am departing east are required to deviate south to the southern district to avoid noise disturbance to the populated areas in both sides of the Victoria harbour.

Finally, flight safety is the biggest concern in every controversy in aviation engineering, a well-designed flight path can totally reduce the probability of aviation accident. Some of the unexpected aviation accident due to uncontrollable reasons such as bad weather and extreme topography. A well-designed flight plan can totally avoid the flight path pass through the extreme topography, also, it should including an extra planning to handle emergency situation. For example, the normal flight path should close to the airports for emergency landing or the aircraft can change the flight to the designed emergency path when facing extreme weather.

While in this task, we need to design the shortest path in the map which has some obstacles with the basic concepts of flight path planning in the above, including flight safety, flight efficiency and other aircraft operation problem. We need to find a specific aircraft model that costs the minimum in the map, including the time cost, fuel cost and consuming of time, in order to design a cost-efficient flight which is very important in aviation engineering.

2. Introduction of the Engineering Tools

• Python

  Python is the world’s fastest growing programming language, not just amongst software engineers, but also amongst mathematicians, data analysts, etc… since it’s very beginner friendly programming.

  It is created by Guido van Rossum in 1990 as a way to write software for the Amoeba operating system. Python is a general purpose, high level, interpreted language with easy syntax and dynamic semantics programming language. Supports multiple programming paradigms, including procedural, object-oriented, and functional programming. Its high-level built-in data structures, combined with dynamic typing and dynamic binding, make it very attractive for Rapid Application Development, as well as for use as a scripting or glue language to connect existing components together. Python's simple, easy to learn syntax emphasizes readability and therefore reduces the cost of program maintenance. Python supports modules and packages, which encourages program modularity and code reuse. The Python interpreter and the extensive standard library are available in source or binary form without charge for all major platforms and can be freely distributed.

  It available on several Operating System including Windows, macOS and Linux.

  • -->Why python is popular:
  • 1. Easy to learn and use

  Python language is incredibly easy to use and learn for new beginners and newcomers. The python language is one of the most accessible programming languages available because it has simplified syntax and not complicated, which gives more emphasis on natural language.

  • 2.Hundreds of Python Libraries and Frameworks

  Due to its corporate sponsorship and big supportive community of python, python has excellent libraries that you can use to select and save your time and effort on the initial cycle of development. There are also lots of cloud media services that offer cross-platform support through library-like tools, which can be extremely beneficial.

  • 3. Big data, Machine Learning and Cloud Computing

  Cloud Computing, Machine Learning, and Big Data are some of the hottest trends in the computer science world right now, which helps lots of organizations to transform and improve their processes and workflows.

  • 4. Mature and Supportive Python Community

  Python was created more than 30 years ago, which is a lot of time for any community of programming language to grow and mature adequately to support developers ranging from beginner to expert levels. There are plenty of documentation, guides and Video Tutorials for Python language are available that learner and developer of any skill level or ages can use and receive the support required to enhance their knowledge in python programming language.

• GitHub

  • GitHub is a code hosting platform for version control and collaboration. It provide a web platform for multiple people to simultaneously write code and come up with new solutions to problems that may arise during the site development process. It lets you and others work together on projects from anywhere. In GitHub, you may 1. create and use a repository 2. start and manage a new branch 3. make changes to a file and push them to GitHub as commits 4.open and merge a pull request. In this group report, we organise and store data in repositories in GitHub. Repositories can contain folders and files, images, videos, spreadsheets, and data sets. We can make and save changes to the files in our repository. GitHub makes it easy to add one at the same time you create a new repository and discuss thing with others.

3. Path Planning Algorithm (Group Task)

i.Find the PolyU Aircraft Model that achieve minimum cost for the challenge assigned to your group (Task1)

a) Introduction

The first task required us to read and analyze the code to find the optimal aircraft model by modifying the data to compare the lowest fuel consumption of the four pre-defined aircraft under the optimal path.

b) Designing Scheme

For the first step, we changed the specific data(See here) from the code downloaded from the class GitHub repository. By studying and analyzing the code, we found that the establishment of boundaries and barriers is based on mathematical function logic.

After making proper modifications to the code, we obtained a satisfactory planning route as the graph shown below.

Then, we embedded the data provided by Task 1 into the code and obtained the fuel consumption data of each of the four models in this model. After mathematical comparison and analysis, we agree that PolyU-A380 has the lowest fuel consumption in this model with the cost of 2396.23.

c) Discussion

We have used the A* algorithm to compare the costs generated by different aircraft models with the same start and end points, and finally obtain the best results.

Such a research method can be extended and applied to the process of aircraft development: By setting different experimental conditions and using the A* algorithm to calculate the costs for different conditions, the most suitable aircraft parameters can be predicted in a comprehensive manner, providing a good reference for aircraft designers.

However, the code is not intelligent enough so far. We tried to let the code compare the data by itself, but failed to do so because the underlying code was too complex. In addition, the path calculated by the A* algorithm maybe not the best since the mechanism of finding the optimal route is based on the closest path between each point itself and the endpoint, rather than considering the whole area. At a later day, we will continue to study in-depth.

ii.Calculate the Minimum Cost Aircraft Model within the Constrains (Task2)

a) Introduction

In this part, our group aimed to find the model that costs least in specific map. To do this, we designed two programs for different targets including time-cost, fuel- cost, time-comsuming area cost and fuel-comsuming area cost. In addition, one(A* Path Algorithm) of the programs, which is improved by our group from A*_search_algorithm whose author is Atsushi Sakai Nikos Kanargias, is to calculate the minimum cost route, and the other one(LP Algorithm) which is entirely programmed by us is to calculate the parameters of the model within the constrains.(See the result directly)

b) Designing Scheme

Through the research, we found that the parameters of the model do not affect the minimum-cost except the time and fuel consuming area.

(It can prove by: Cost = (C_T * d_T + C_F * d_F) * Distance(a) + C_T/F_Area * Distance(b). If only C_T * d_T + C_F * d_F = Constant ≠ 0, the shortest Distance will not change)

With this idea,

• For 4 constraints with 2 variables, there is no need to consider the path. We can use "Linear programming(LP)" to compute the approximate parameters.
• For 4 constraints with 6 variables, we have to use A* algorithm to compute the best path due to the changeable T/F_Consuming Area. However, in consideration of the parameters which are integer and the simplification of the constraints, we can easily use the Enumeration Method to find C_T, d_T, C_F, d_F, and then use A* algorithm to enumerate all eligible values of T/F_Consuming Area.

c) Algorithm Implementation

• LP Algorithm

  • List of key function:
  • Search for Cross Point
  • Calculate Target Line
  • Display

  • --> Search for Cross Point

    Substitute every x in domain into every Line Equation. If |f(x) - g(x)| --> 0, then mark the point(x, f(x)) and store it into list A. Adjusting the precision to ensure the efficiency and accuracy is the key point. The accuracy will decrease if the slops of the two lines are too similar.

  • --> Calculate Target Line

    First, determine whether the point in A is in the spacific area between certain line and xy-aixs and store the results of every line into list B. Take the intersection of the B, and then we can get the possible points.
    Second, find the minimum point using the equation C_F = (C_T * d_T) / d_F(i.e. f(x) = (a * x) / b. However, there may be some BUGs like no appropriate point or the result which goes to infinity. We just consider general condition and there is considerable scope for improvement.

  • --> Display

    Show the result with pattern and figure.

• A* Path Algorithm

  • List of key function:
  • Basic Path-Computing Function
  • Enumeration and Comparation Function
  • Display Result

  • -->Basic Path-Computing Function

    Theory: Start at a curtain point, retrieve every direction to find the next minimum point (The direction closest to the goal will be the first to be retrieve), move to next point and repeat above step.
    Actually, this algorithm is based on Breadth-First Search, but will firstly search the point that has the shortest distance to the goal. That can improve the efficiency in some cases.

  • -->Enumeration and Comparation Function

    Enumerate all possible value within the constrains and find the minimum value for the paramaters.

  • -->Display Result

    In this part, we will show all the infomation including computing process, approximate paramaters, the minimum cost, the new and origin route.

d) Result

Through computing, we got following model and data:

4 Constraints with 2 Variables
	𝐶_𝐹	d_𝐹	𝐶_T	d_T	C_C	d_F_A	d_T_A
Group 1 Aircraft Model	20	5	20	5	10	5	5
	Total Cost: 24448.52559935244
4 Constraints with 6 Variables
	𝐶_𝐹	d_𝐹	𝐶_T	d_T	C_C	d_F_A	d_T_A
Group 1 Aircraft Model	9	2	1	8	10	9	1
	Total Cost: 4274.2349903979

Figure 1: The Result of 4 Constraints with 2 Variables

This is the result computed by LP Algorithm shown as figure.

--------------------------------------------------------:P---------------------------------------------------------------

Figure 2: The Progress & Result of 4 Constraints with 6 Variables

On the left side, there is the progress of computing and the result of the paramaters.
On the right side, there is the path of new model(red) and the origin model(gray)

e) Discussion

We used linear programming algorithm as well as A* algorithm to study the aircraft model and successfully found a suitable aircraft model under the constraints. In the process of our research, we successfully developed the LP algorithm and implemented the automatic comparison function of the A* algorithm which means we have established a diversified evaluation system to calculate and predict aircraft design from various aspects. This has helped us tremendously in studying the aircraft model from a different view.

Such a diversified research system is of great significance in the development of real aircraft. For example, Linear programming can find the most suitable combination of parameters within the constraints from the perspective of multi-parameter variables; The path planning can analyze the cost-effectiveness of the aircraft model from the perspective of flight cost; Other different approaches can be used to analyze the aircraft model from different aspects. Therefore, a diversified evaluation system can calculate and analyze the model comprehensively, which makes the aircraft design more rigorous, safe and economical.

However, we currently have many shortcomings. For instance: LP program is not well developed to handle some special cases correctly; The research method including LP program and A* program can currently only deal with a small number of simple parameters which cannot be synthesized to analyze a large number of aircraft parameters since these programs have narrow application scope, high specificity and poor adaptability. In future studies, we will aim at multifaceted analysis to design methods and programs that can take into account multiple parameters and conditions for evaluation.

iii.Design a minus-cost area for the route (Task3)

a) Introduction

In this task, our group has designed two algorithms to find the minus-cost area in order to decrease the cost of flight. Based on the limitation that the maximun minus-cost area is 16 grids, there are two programs, one (Discontinuous Area Algorithm) of which is to calculate discontinous area, and another one (Continuous Area Algorithm) is to calculate continous area. (See the result directly)

b) Designing Scheme

Through analysing, we believed that covering the minus-area on the route which has worked out is the efficient way to reduce the cost of flight.

According to this principal, we can

1. Compute the route of flight without covering the minus-area.
2. Traverse the route which has worked out and record the data.
3. Process and compare the data, get the result.

c) Algorithm Implementation

• Discontinuous Area Algorithm

  • List of key function:
  • A* Path Algorithm
  • Discontinous Area Algorithm
  • Display

  • --> A* Path Algorithm

    Search for the minimum-cost path.

  • --> Discontinous Area Algorithm

    1) Traverse the path, while recording firstly all slash paths and secondly all straight paths.
    2) Append all the slash path into minus-cost area list. If there is still avialable space of the list, append the straight path into the list.
    

  • --> Display

    Draw all the blue areas recorded in the minus-cost list on the map.

• Continuous Area Algorithm

  • List of key function:
  • A* Path Algorithm
  • Continous Area Algorithm
  • Display

  • --> A* Path Algorithm

    Search for the minimum-cost path.

  • --> Continous Area Algorithm

    Traverse the path. Different from the Discontinous Area Algorithm, this traversal is like a "snake". The "snake" will firstly come out from the start point. Then with the head of the "snake" moving on, its body will come out and follow one by one (Maximum length is 16 grid). If the "snake" meets the fuel/time cost areas, it will disappear and come out from other sides of the areas.
    
    During the process of traversal, we have to record the position where the "snake" can reduce the cost most.
    

  • --> Display

    Draw the blue "snake" at the position on the map.

d) Result

Through computing, we got following minus-cost area:

• Discontinous Area shown below:



• Continous Area shown below:

e) Discussion

We used the method that traverse the path which had worked out and successfully find the most appropriate minus-cost area.

To achieve this goal, we have designed some algorithms that can calculate the path in any condition if only the path works out. Furthermore, we also considered two cases, one in which the area is continuous, another one in which the area is discontinous. In this way, we can get more diverse results.

If this method is improved, it can also be extended to other aspects of area settings, including but not limited to setting optimal climbing and descent areas and calculating the best areas to fly in complex weather conditions. In this sense, it is of great significance for a real flight planning.

However, in the course of our research, the program we developed is only applicable to the linear search & calculation, which has huge limitations. In the future study, we will focus on more situations, such as planning areas on a map where value is unevenly distributed, or planning two-dimensional areas on a map. We belive that the research in this direction will have greater significance.

iv.Additional Tasks (Task4)

a) Adding Checkpoints

Introduction:

This task simulates the planning of a multi-node route in a flight plan.

Methodology:

After the checkpoints were set, we can achieve it easily by planning between every two points：

Result:

Discussion:

Adding checkpoints is a rather easy and straightforward task compared to the others. The most critical part of it is to understand the basic principle that how the algorithm computes the shortest part. Long stories short, we need to know that each shortest path is derived from the other shortest paths. The shortest-circuit path is still the shortest after cutting off the end (National Taiwan Normal University). Therefore, we just need to turn the task of adding checkpoints from a long path into a calculation of the shortest line between each node and connect them together.

This task examines our ability to transform the problem. By changing the perspective of the problem, the difficulties can often be solved easier than expected.

b) Changing Environment

Introduction:

This task simulates the performance of the A* algorithm in a complex environment.

Methodology:

a) Map generation: Use random numbers and set the probability for each point generation.
b) Path calculation: use A* algorithm and remove the slash direction

Result:

Of course, one day, there will be a chance that the map will then look like the following (www

Discussion:

To simplify, this task includes two main points. Firstly, the task requires us to introduce random numbers to create the environment; Secondly, it requires us to restrict some performance of the code to ensure accessibility. The first requirement enables the code to create a random environment, while the second requirement aims to test the algorithm's ability in planning for the shortest path.

In the practical aspect, we agree that we have generated a simple idea to form a random environment, which is unneglectable in the flight simulation. The randomly generated environment is also a big challenge for the algorithm. However, although we limit the density of the barriers as well as create some "buff" for the path planner to prove the accessibility of the code, we still can not guarantee that there is always a path between the starting point and the endpoint. We generate the code to let it regenerate a new environment as well as recalculate the ideal path with the shortest distance. When you meet an error in finding the path, a funny message box containing a Chinese notification will be shown on the screen, which is due to the codes shown in the image below.

To make the programming more funny, we add a possibility for the code to automatically generate a "wall" to block any possible path. This is in fact related to the code's recauculation capability. However, the A* algorithm prefers to erase memories and regenerate the path due to its design, an update version called D* will be introduced below.

c) Comparing Algoritms

• a. A* algorithm

  A* algorithm absorbs the advantages of Dijkstra algorithm. Similar to Dijkstra algorithm, A* algorithm also adopts priority queue. What different from Dijkstra is that A* algorithm sets priority follow the equation "f(n) = g(n) + h(n)", which can optimize the tranversal efficiently and reduce the time consumption in some cases.

  Advantage:

  • A* algorithm can substantially optimize the process of searching and reduce the time of calculating, which can improve the capability of path planning in all areas like flight planning.

  Disadvantage:

  • A* algorithm is mainly suitable for static calculation. If there are some changes like obstacles suddenly appearing in the path which has worked out, this algorithm have to recalculate the path. That will cause the time comsumption and effect the performance of computing. If there is no optimization for A* algorithm, this algorithm will be difficult to apply for dynamic planning.

• b. Dijkstra's algorithm

  Dijkstra's algorithm is an algorithm designed by computer scientist Edsger W. Dijkstra in 1956 that uses a similar approach to breadth-first search to solve the shortest path problem for a single source in a given environment (especially if the environment is already given).

  The essential difference between Dijkstra and the breadth-first algorithm (BSF) is that BSF accesses the nodes in the container in an artificially predefined order, while Dijkstra accesses the node with the lowest cumulative cost g(n) (which is the current best estimate of the cumulative cost from the starting node to node "n") in the current container.

  The Dijkstra algorithm guarantees that the node it has visited is the least costly node in the container at the current moment, thus ensuring the completeness of the entire algorithm.

  In fact, the A* algorithm we used in the previous task is a variant of Dijkstra's algorithm. This new code takes each new point as a source and produces a shortest path tree by finding the shortest path between this endpoint and all other nodes, which achieves the effect of improving efficiency. However, since its search area is relatively limited compared to Dijkstra's algorithm, the path found is not necessarily the "shortest path".

  
• c. D* algorithm

  D* algorithm is based on Dijkstra algorithm. The difference is that the D* algorithm will first start searching from the end point. After initial planning, if an obstacle is detected, the program will make local adjustment to avoid the obstacle. Until it reaches the end, the program ends.

  1. • Static planning

       In the initial planning, the D* algorithm will start from the end point. Based on a certain point, after searching the points around the store and adding the searched points to the Openlist, the D* algorithm will preferentially traverse the points according to the k-value from smallest to largest and point the pointer to another point whose k-value is smallest.
       Therefore, D* algorithm is much less efficient than the A* algorithm and does not use its raise and lower part of the algorithm in the initial planning process. Therefore, the D* algorithm does not realize its advantage in static planning.

     • Dynamic planning

       After the initial planning, when an obstacle is detected and blocks the route, the D* algorithm will first diffuse the RAISE state (indicating that the actual value of the current point is higher than the originally calculated point) from the obstacle point to the surrounding points, until it diffuses to the point or path that can reduce the actual value, and diffuses the LOWER state (indicating that the actual value of the current point can be reduced by other points) to the diffusion source, until it gets the new shortest path, then ending the obstacle avoidance planning. In this way, the D* algorithm can efficiently re-route when the route is blocked, enabling dynamic planning.

       Of course, to reflect the efficient dynamic planning of D* algorithm, the program must be run on a larger scale map to ensure that the area that its RAISE state spreads takes a very small percentage of the map, otherwise the efficiency of D* algorithm replanning will not be comparable to that of A* algorithm replanning.

       In order to implement dynamic planning to demonstrate the function of D* algorithm, group member QIN Qijun studied a lot of D* theory literature papers, and modified part of the algorithm theory in the literature papers through a lot of experimental data and reasoning. Finally, he independently finished a program based on D* algorithm and almost implemented the function of dynamic planning. The dynamic planning function shows below:

  2. Algorithm Implementation

     • D* algorithm program

       • Structure of program:
       • MAP
       • OPENLIST
       • DSTAR.state_process
       • DSTAR.obstacle_sensor
       • DSTAR.run

       • --> MAP

         To record the information of every point on the map.

       • --> OPENLIST

         We use the minimum binomial heap to implement the OPENLIST function and assign key values (not k values in D*) to all elements in OPENLIST to maintain the uniqueness of the elements and to update the element values.

       • --> DSTAR.state_process

         To process current point and build the relationship with other point.

         NORMAL state:

         Preferentially tranverse the point which is nearest to the end point until it reaches the end. That is similar to dijkstra.

         RAISE state:

         That means current point has changed into obstacle or the value increases. Need to diffuse the obstacles information to surrounding point and to find a point that can reduce the value of current point.

         There are 3 cases in the next point: 1.New point. 2.This point points to the current point but the value of the next point plus the distance between the two points is not equal to the current point. 3.This point does not point to the current point and the current point can reduce the value of the next point.

         LOWER state:

         That means the value of current point can be reduce by surrounding point which is closer to the starting point and diffuse value-decreasing information to the new obstacles. In addition, change the direction of that point.

       • --> DSTAR.obstacle_sensor

         This is a function for detecting obstacles. In practical applications, we can pass in signals from actual sensor devices. If the sbstacles block the original route, the program will execute obstacles avoidance function.

       • --> DSTAR.run

         Integrates pathfinding and obstacle avoidance functions. It is the main function of DSTAR.
  
  
  3. Development History

     
     

     Limited by our technical level, The total development time of the D* algorithm program was about a month. At the beginning we used Mr. Atsushi's D* algorithm template and referred to a lot of literature papers. Everything went well in the initial planning process. However, when an obstacle suddenly appeared, the program could only be replanned if the obstacle was smooth, otherwise the program would hang.

     

     
     So we created a small map and then did a lot of debugging. We obtained a lot of experimental data including but not limited to the processing of each point to the next point in different situations, the change of data near the diffusion source at the beginning of diffusion and the change of the pointer during the diffusion process. Eventually we boldly modified and adjusted part of the algorithm in the diffusion process, and successfully implemented obstacles avoidance action.

     

     
     However, such forced changes may create potential BUGs. So there are lot of experimentation and modification needed to ensure the program's viability.

  4. Problem still unresolved

     
     

     Currently there is a situation that causes replanning to hang, that is, when the two replanned diffusion ranges overlap, the last diffusion may form a ring in the previous diffusion range, causing the program to spin around in the ring.

     We speculate that it may be due to the fact that the h-values of some points were modified and not equal to the k-values during the next diffusion, causing these points to interfere with the program's judgment during the next diffusion.

     If conditions permit, we will try our best to fix BUGs and improve the program.

• Discussion
  We have carried out a certain degree of comparison and study of these three algorithms, obtaining the advantages and disadvantages of these three algorithms as well as the scope of application.
  During the development process, we created the same map model and ran the three algorithms in the model while comparing them. In addition, we specifically developed the D* program for representing the dynamic planning function of the D* algorithm. However, during the development process, we encountered a situation where the function could not be implemented referencing the literature. We used the "modeling and large-scale debugging" approach to modify the program based on the feedback from the debug data, and finally implemented the function successfully.
  Furthermore, we have made a greater program design in this study. We improved the algorithm of D* literature to enable the algorithm to implement dynamic planning in more complex environments. Also in the D* program, we added min-heap data structure, which is able to optimize the processing of the minimum k values in the queue. This greatly improves the efficiency of the program in dynamic planning.
  In real life, A* and D* algorithms (and their variants) have wide applications. For example, A* algorithm is often used for common pathfinding problems in applications such as video games and the variant of D* algorithm has used on the Mars rovers Opportunity and Spirit developed by NASA.
  However, the current D* program is not complete and has many bugs, and is not as efficient as we expect it to be. In the future we will focus on fixing bugs and optimizing the program.

4. Summary

• This freshman program gave us a great challenge. However, we gained a lot of knowledge and experience through this freshman project. From the beginning, we had never touched path planning, never learned python, and didn't even know how to use programming software. In order to complete the task, we had group discussions and kept self-learning. We review a lot of information and do the tast while learning. That led us to learn a lot of algorithms and principles, and gain a lot of experience. In the process, we also developed a passion for programming and algorithms. If there's still a chance, it's sure we'll keep trying to improve ourselves and reach a higher goal!
• We have learned:
  • How to use VScode and Github
  • The Basics of Python
  • How to use Atsushi's A* algorithm to complete the task
  • How to edit the A* algorithm to adapt other tasks
  • Other more algorithms
  • How to program through review literature papers (like D* algorithm)
  • How to use HTML to write the report
  • ...
  • However, the thing that most matters is that we cultivate the ability to learn on our own, to break through from internet resources and to work together as a team to complete tasks with an incredible 1+1>2 effect.

5. Contributors & Reflections

LIN Ju @Thorkee

The process of completing this project was very rewarding. We spent many nights in the library discussing the project until the library closed. Although we did not learn much hard knowledge of path planning or the algorithm in class, we gradually cultivated our independent learning ability in this process, and kept learning from the previous experience and wisdom of the pioneers in this field under the requirements of each task, and created incredible results.

As the group leader of this group, I did not do a good job in many aspects of leadership. For instance, I did not do a good job in mobilizing members' motivation. I have been reflecting on this and learning from it. I believe I can do better in other tasks in the future.

I would also like to take this opportunity to thank my friend QIN Qijun @QuintinUmi. He has a great passion and extraordinary understanding of algorithms and code. He has made a great contribution to the completion of the task. Without him, our task would not have been completed as well as it is now.

At the same time, I hope that other groupmates could be more motivated to participate in the task. You have done a good job but you could have been more involved in our tasks if you showed your passion earlier. Don't say that it's hard. Every difficulty can be conquered as long as we have passion for it. Equally important, taking a proactive attitude to approach the assigned task is the golden key to reaping great success.

Lastly, I would like to thank Dr Li-Ta Hsu and Dr Wen as well as Teaching Assistants for giving us such a challenging task. I am very satisfied with the course setup and hope we can continue to work together in the future.

CHENG Pak Hin @marcus2405

This my first group project to do studying in University, I have learnt a lot through this project. In the task, I and my groupmates are required to collaborate to design the shortest path for a flight plan without crashing on the obstacles. Also, we are needed to calculate the time and cost needed and find out which aircraft model is the most suitable for the flight. We used Python and GitHub to design the flight path. The task required us to read and analyze the code to find out the optimal aircraft model by modifying the data comparing the lowest fuel and time consumption. We used the A* algorithms to compare the costs of the different aircraft models to find out the most suitable aircraft model. Of course, we are not getting the result easily. We have attempted many times. Since this is the first time for me to use Python and typing code, it was quite hard for me typing code on Python at first. But now, I’ve already learnt the basic concept behind the code and how to use them. Besides the technical stuff, I have learnt more about collaboration. During the task, I and my groupmates had many discussions of what parts each of us should do and how to make the group project better in result.

QIN Qijun @QuintinUmi

This project is the first one I have participated in since I started school.

This project brought me not only technical improvement, but also teamwork, self-learning ability, perseverance, ability to find solutions to problems... The combination of these qualities. It really makes a person grow and mature.

In the process of overcoming the project, there is nothing I have experienced more than the word "self-learning". When I was studying algorithms, writing programs and reports, I was often in a state of "learning by doing, learning from doing", not knowing how many difficulties were waiting ahead. But these challenges whetted my appetite for learning algorithm. The intensity and initiative of my study was comparable to my high school days. Finally, live up to expectations, achievements in lage numbers. In this sense, the way Dr. Li-Ta teaches is of great benefit to hardworking students. This way gives us space for independent thinking, self-learning, and teamwork, which can give great growth

In the future of my life, I will also continue to be looking for my goals, continue to pursue my passions, and devote my passions to the pursuit of my goals!

HUI Chiu Ming @edmondhui04

In the past few weeks, we worked together on our group project. Since we are freshman in PolyU, we might both have our own personal activities or school academic works to do, I appreciate all our groupmates are working very hard on this project and take the responsibility to join every group discussion and finish their own distributed works.

Charles is very take care of us, he has the team leader characteristic to guide our works, when we are facing difficulties, he always picking times to give assistance or even troubleshooting for us.

Otherwise, in this project, I mainly focus for the collecting research or information for the path planning, writing some codes to form the images then data analysis, finally giving assists and providing some advices for my groupmates. I’ve learnt about the important of path planning, how to use the coding to form some images and using Github to work togethers.

Finally, This project increase my interest about aviation engineering to learn more and read more.

CHENG Wai Ching @Chengmm565

It was my first project when I got into the university. It was such a great experience for me to learn from peers and the apply of Python and GitHub. I am responsible for the part of additional tasks which are adding checkpoint and changing environment. In this task, I have to program the route plot from Python and figure out the methodology of adding the nodes. Besides, I have to make changes to the map and finally find the shortest and low-priced path in a complicated environment. Since the coding from Python was quite challenging for me so I asked for assistant from my group mate. Furthermore, I searched and collected information of A* algorithm and Dijkstra’s algorithm from the internet and also some educational video clips from YouTube.

From the group work, we learnt to share different ideas and gained programming skills. We got together and tried to brainstorm a better decision. Our group leader Charles gave us a big support in the group work and he corrected the mistake we made on readme report. It was a precious chance for us to learn from each other.

6. References

1. Atsushi, S., & Nikos, K. (2020). A* grid planning. Retrieved from https://github.com/AtsushiSakai/PythonRobotics/blob/master/PathPlanning/AStar/a_star.py
2. Atsushi, S. (2020). Grid based Dijkstra planning. Retrieved from https://github.com/AtsushiSakai/PythonRobotics/blob/master/PathPlanning/Dijkstra/dijkstra.py
3. Atsushi, S. (2020). D* grid planning. Retrieved from https://github.com/AtsushiSakai/PythonRobotics/blob/master/PathPlanning/DStar/dstar.py
4. An introduction to GitHub. Digital.gov. (2020, June 18). Retrieved November 11, 2021, from https://digital.gov/resources/an-introduction-github/.
5. Tyagi, N. (2021, February 15). What is Dijkstra's algorithm? examples and applications of Dijkstra's algorithm. What is Dijkstra's Algorithm? Examples and Applications of Dijkstra's Algorithm. Retrieved November 10, 2021, from https://www.analyticssteps.com/blogs/dijkstras-algorithm-shortest-path-algorithm.
6. 演算法筆記 - Path. National Taiwan Normal University. Retrieved November 11, 2021, from https://web.ntnu.edu.tw/~algo/Path.html
7. Stentz, A. (1994). The D* Algorithm for Real-Time Planning of Optimal Traverses. CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST.
8. Carsten, J., Rankin, A., Ferguson, D., & Stentz, A. (2007, March). Global path planning on board the mars exploration rovers. In 2007 IEEE Aerospace Conference (pp. 1-11). IEEE.