0 Comment

AbstractWe design an software to find optimal(shortest) path on the University of Minnesota map by using the A* algorithm. Using GUI (Graphical User Interface) to visualize the path on the map and print the list, which contains the transient nodes. It is definitely efficient way for students to make route planning in the campus. The approach supports that query the shortest path and manage the time in the campus. Maps are kind of diagrammatic form that represents physical features such as buildings and roads, and maps play an essential role in the development of civilization. Most of people are familiar with using maps to find routes and locate their position on the maps. However, it is very challenge to find a shortest path in the real world. Therefore, using computers and algorithms are efficient ways to solve route planning problems. Using graph theories to take the place of real buildings and available roads with nodes and edges, then a transportation network has been established by connecting them. Meanwhile, computer software can generate a shortest path in such transportation network. The path shows the optimal solution in the corresponding transportation network, what is more, the tool we designed should be tested against real world, complex situation in order to detect any bugs existing in it.Map is a graphic way to represent spatial concepts. A type which people most familiar with is transportation map. Map is a medium of interaction between human and environment. That is because vision of human cannot satisfied human when they make plan according to environment. An accurate map could help human to learn where they are, and make correct decision. For the record, Napoleon Bonaparte did that we owe the first systematic use of maps in the conduct of war. \cite{p2}Accurate information on map helped French Emperor to coordinate geographically expansive campaigns and discrete armies in the field. They indicate positions of enemy armies and do prediction by labelling on map. By calculating distance and highlighted important topographical features on map, predication could be much more accurate. As “a means of visualizing and managing the future,” the Napoleonic map was “the central part of an information-transformation system”\cite{p3}Technology helped map develop more quickly.  Map helps human learn a more accurate world, and also makes life of human more convenient. For example, when students join a new university, or they want to know about campus, students could use visual map software installed in smartphones to get rough idea about it. Map cannot show all detail about each building in campus but it could provide students the most accurate shapes of buildings in vertical view, distance between them and relations of positions. All these information could help students to learn their campus better. However, it is difficult for some of students to find a route between two location in a complicated campus which is with a big area, like the University of Minnesota. Current technology is able to provide students with a shortage and accurate path showed on visual map installed on phone. Besides that, its application makes work more efficient when people want to get some locations where they never been.Such technology always be called route planning. Route planning is for computing most efficient route which contains several nodes by making distance travelled or time minimum. Time could be calculated by distance and speed limiting. Therefore, the way to make distance of route as minimum as possible is the most interesting and pivotal part in route planning. As concept of route planning stated, there will be several nodes on route. The key of task is what standard for choosing next node where user can access from start location. Or what expectation to node which is on the shortest route. Absolutely, all of these needs computing by algorithm. Fortunately, There are some algorithms which are efficient for computer to solve route planning.The PNA stands for personal navigation assistants, also known as Personal Navigation Device or Portable Navigation Device (PND) is a portable electronic product which combines a positioning capability and navigation functions. The features of the 3rd generation of the PNA system include determining locations of users and indicating path planning.\cite{p4} To determine the location of users, the software will define N to represent the streets system, N contains a set of curves, which can be called arc as well, then set the position P in the transportation network. The algorithm can find nodes, which are close to P, and find a series of arcs that are incident to the nodes. Using a minimum norm projection to find the closest arc, and calculate the minimum distance between p and the line segment. \cite{p4}Since there are many nodes on the transportation network, the problem can be simplified as making decisions to nodes surrounding current nodes. \cite{p5}These kinds of problems called combinatorial optimization problems, which build a solution step by step. At a step, a single element will be added in the current solution which is partly under construction.\cite{p6}The “Least-cost”, which represents the shortest distance of the route, is also always be treated as an optimal solution in the route planning problem. Greedy algorithm for minimization always chooses one of the least cost. In the greedy algorithm, among feasible elements, the algorithm would select an element with the least cost and put it in solution under construction.\cite{p6} Applying the greedy algorithm in route planning, start with object S, naive greedy will choose an object which is closed to S. However, we do not know if the object is an element of the optimal solution. What is more, naive greedy heuristic pay all attention to current cost and ignore target object T. Therefore, advanced greedy algorithm called oriented heuristic greedy heuristic can solve the shortage. Let us represent current location is L. When it selects next object O, the oriented greedy heuristic will consider the value of the distance between current location O and target T. Heuristic will choose object O when ( dist(L, O) +dist(S, O) + dist(O, T) ) is minimum among all possible choices. \cite{p5}Instead of focus the cost of a small part in the path, oriented greedy heuristic is better to reduce total cost, which has a much higher possibility to find a route that the user feels satisfied. However, greedy has its limitation. Like real-world is complicated, if we add more constraints to solutions like avoiding some specific object, the greedy approach sometimes cannot guarantee the optimal solution because the solution might not satisfy all constraints.\cite{p7}Dijkstra’s algorithm aims to find the shortest paths between nodes in a graph. According to the research paper “Customizable Route Planning” written by Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck, they mention that Dijkstra’s algorithm still exists weakness and it can be modified. They brought up a new system that allows real-time queries, which has fast customization and keeps very little data for each metric. Compared to the previous technique, their approach implements PCD (Precomputed Cluster Distances) in their basic algorithm and starting with bidirectional Dijkstra’s algorithm searches restricted to the source and the goal. Using ACT preprocessing to pick X vertices as landmarks, and stores distances between these landmarks and all vertices in the graph to guide the search towards the goal.\cite{p8} All in all, their algorithm speedups the original Dijkstra’s algorithm to a new peak.The differential evolution algorithm (DE) is a kind of approach to find the optimal path. According to the academic journal “An Improved Differential Evolution Algorithm for TSP Problem”, the authors provide an enhanced algorithm to solve this problem. Their algorithm improves the convergence speed and optimal quality by regulating the integer sequence to the mutation process instead of using the original crossover operator. The procedures to build this algorithm are creating an initial position by using greedy algorithms, modifying the DE algorithm by regulating integer sequence, implementing Liuhai’s crossover algorithm to generate the best solution. \cite{p9}The algorithm has a faster convergence rate and can get an optimal solution or approximate optimal solution.Moreover, the heuristics search can be used for route planning. According to the journal “Evacuation Route Planning: Scalable Heuristics”, the authors Sangho Kim, Betsy George, Shashi Shekhar presents innovative heuristics scalable to solve route planning problems with very large system. They brought up the concept called “Intelligence road”, which aims to find the optimal route rather than optimal “schedule”.\cite{p10} The Intelligence road heuristic(ILR) applied to the CCRP algorithm, they modified CCRP by adding some features to implement load reduction formula. They mention that compared with CCRP, ILR heuristic makes more efficient than CCRP because it can skip many iterations that do not produce new routes. This is why the ILR heuristic algorithm can involve more complex network systems.  The project is to solve the problem that find a shortest route between two location among all nodes on the map. In simplified situation will be discussed in project, A* algorithm, or called A* search is more easy to handle and it is efficient. It evaluates node with total cost, which denoted f(n). What decide f are costs which are denoted g(n),the cost to reach the node,  and h(n),  the cost to get from the node to the goal. In mathematic, equation is: f(n) = h(n) + g(n). During selection of nodes, f(n) is supposed to be estimated cost of the cheapest solution through node n. Different from uniform-cost-search which only consider value of g, A* search is both of complete and optimal. Figure shown above contains pseudocode and main idea which is way to solve route planning with A* algorithm. From start node which is also current node, all of its neighbor node will be put in open list for choosing. Absolutely, algorithm will choose the node with lowest f value, set it to new current node.  And it will be put in close list. Then denote last node as parent node, which is for make connect between nodes on solution. Repeat these steps until target node appear in close list. If open list was empty, which means there is no more choice for solution. Algorithm will fail to find a solution. Algorithm will record g and h value of all node in open list and go back to check if there is any node in open list will be better than current node. When algorithm get the path to target node, solution is found. Algorithm will backtrack to start node to label all nodes on route by using parent nodes we set during searching.The figure 2 shows the main source codes in the the file. In the file, we import JFrame from the java library to pack the other java files.,,, SearchPath are Object-Oriented Programming files. The main structures and algorithms wrote in the file. is a helper function, which stores all possible nodes. Map.jpg is a the university map on the google maps.The strategies of designing this software are: Marking several points nearby “Northrop” in the university campus map and give them coordinate points. The Figure 3 shows the example that adding the coordinate points on the campus map. Then, searching all the possible paths in the each position, and add them in the paths (Figure 4). And the Figure 5 shows the map after marking the points and their possible paths. In the figure 6, we use the Manhattan Distance to get the g and h value, according to the A* algorithm, we were looking for the path, which has minimum f value (f = g + h). These two “Manhattan Distance” functions are to calculate the length between current position to the starting position or ending position. We defined four unit vectors to represent the direction to expand, and add the starting point in the min-heap.(Figure 7) As I mentioned above the min-heap file is a helper function to return the node, which has minimum f value (the purpose of A*). In the for loop, we recorded the node that we visited once to avoid repetition. The iteration terminates when there were no nodes in the min-heap.  In the figure 8, we iterated four directions in the inner loop, if the nodes is the end then break the loop, and to determine whether expand or not (only the node is SPACE).If the new point has already in the heap then keep updating the g value, otherwise add it to the min-heap. Until expending the node to the end point, Figure 9 shows the loop to find the path by searching their parents. In the figure 10, printPath() function, printing the passed nodes from starting point to the ending point, and showing their coordinate points.After testing a lot of examples, outputs are satisified expectation. It could find shortage path between two nodes selected. Some different conditions shown below. In first condition, ramdom output shows route from P8 to P20. At beginning, P8 has neigbors which are P0,P7 and P5. It selects P5 because it is easy to see f value of P5 is smallest. Then algorithm select P10 in same way. In selection between P23 and P22, algorithm chooses P23 because it has smaller f value. It is correct. With same horizontal distance to P20 and P8, P23 has smaller vertical distance to start and target nodes. f value is calculated in Manhattan distance which needs both of vertical and horizontal distances. Absolutely, P23 will be selected with smaller f value. And it is best solution even in reality. The route is perfect to expectation. Next we choose to test the most complicated condition, from P0 to P16. Reason why choosing these two nodes is there are more choices during search because both of them located in catercorner position on map. It is obvious that algorithm find best solution successfully. Based on condition 2, condition will test if outputs are same if swap start and target node. As results shown and route on map, It still complete task successfully. If start and target node are same, algorithm doesn’t need to find route between them. It would be treated as an error because user sometimes did mistake when input address. Output shows no route on map and reminder user input error in text output.Route planing can be treated as a combinatorial optimization problem. In selection of object, which adds in current and partial solution, greedy search will focus on both cost to next object and total cost from start object to target. In addition, modified Dijkstra’s algorithm aims to speedup the regular search algorithm. Improved Differential Evolution Algorithm has faster convergence rate and can get optimal solution or approximate optimal solution. Scalable Heuristics can solve more complex network system. All in all, Learning from existence algorithm is beneficial for humans to find more optimal solution.