The second research article I read recently is Adaptive A* Algorithm for Dynamic Routing, and after analyzing it, it totally changed my perception of navigation apps (Google Maps) used in everyday life and problem-solving.
I use standard GPS routing daily (as well as the overwhelming majority of people). It is very effective in searching for the shortest distance between point A and point B. Nevertheless, reading this article, I was exposed to a critical weakness of the conventional navigation, particularly in electric vehicles (EVs): the most direct line is pointless when it gets you stuck with a flat battery.
The Adaptive A* Algorithm is an autonomous, forward-thinking navigator instead of just adding up a fixed, static route before getting in your car. You give it a place to go, and it actually tracks real-time traffic, battery depletion, and where charging stations are, and it changes its course on the fly with minimal or no human intervention.
The Brain of the Revelation of the Algorithm. I had to understand how this algorithm was able to pull this off without it having to freeze or even take minutes to recalculate. Coincidentally, developers are improving the traditional A search with a very dynamic brain.
This is a system that depends on some brilliant upgrades, which are broken down in the paper:
Dynamic Heuristic: Standard A* This is based upon a fixed heuristic (guess) of the distance to the goal. Adaptive continuously changes this guess according to changes in real life, such as sudden traffic jams or a reduction in temperature, to affect the battery of the car.
Prefers Energy over Distance: It does not only consider miles. It compares the cost of a route depending on the energy consumption. A steep and short hill may be more expensive than a long, flat road.
State Preservation (Memory): This was the most interesting part to read. When the map is modified, the standard algorithms discard all the information and compute everything afresh. Adaptive A stores the portions of the map that were not altered, which saves tremendous units of processing power. It is a literal shortcut to the plan redraw and trying to start afresh.
Of course, the dynamic navigation system cannot be tested simply by providing a question regarding whether the system has reached the destination. The authors described the comprehensive method of evaluating this algorithm. Instead of just considering the last route, they consider the AI because of computation time (how fast can it recalculate in milliseconds?), energy efficiency (saved battery over standard routes?), and nodes explored (how well did it search the map without exhausting its memory?).
Restrictions are possible, but it is not all perfect. The article was rather categorical regarding the complexity of real-life implementation. But the largest problem is that of Data Dependency--the algorithm is as good as the live traffic data and weather data it is fed with. The adaptive nature is disrupted in case of sensor malfunction or the loss of the 5G connection. The other issue is the computation cost of the car's internal hardware; the continuous updating of huge graph networks needs heavy processing power.
This paper was a summation of it during my AI course. We have just been literally writing code in Python to create graph networks with NetworkX to trace the routes in cities with BFS (Breadth-First Search) and DFS (Depth-First Search). Surprisingly, this paper applies the very concepts that we study in the classroom, the cities being the nodes and the cost of the path (weight) being the edges, and scales it to the real world. As opposed to a plain and straightforward map of Romania, these algorithms follow delicate and dynamic digital road systems to hit their targets safely.
It is a truth to say that when I first saw the enormous mathematical equations that were the heuristic updates in the paper, they looked to me like an entanglement of complex calculus. But just to have a sample of the subject, I decided to save the PDF at Google NotebookLM and asked it to explain the "adaptive" update step simply. It instantly gave me an analogy of genius: it equated the algorithm to a driver who is presented with the sign that the road is closed and merely recalculates the ETA of just the impacted streets and does not forget the entire map of the city. Even that experience superimposed all the dense academic wording and made the entire graph math understandable.
The Adaptive A* algorithm is not only an ingenious line of reasoning but also the basis of intelligent, self-directed transportation. And then, when we have read this paper, I am most impatient to find out how we write these dynamic heuristics ourselves.
And a short video summary in which I further explained what I researched in this research paper.
Video:
I would like to thank my teaching assistant, @raqeeb_26 who assisted in exploring the work relating to the research.
Top comments (1)
Some comments may only be visible to logged-in visitors. Sign in to view all comments.