Introduction

The efficient transportation of matter across short and long distances have long since been of importance to human society. In the modern day, countless forms of transportation exist all around us: cars, planes, trains, as well as in the services which involve said transportation, such as delivery and public transportation services. As of the status quo, most of these operations across the world largely remain suboptimal or inefficient.

In recent years however, the work to automate and optimize these processes through artificial intelligence has seen a drastic rise - examples being self-driving cars, and autonomous delivery services. This project aims to delve into this rapidly growing field of autonomous pathfinding algorithms and their possible applications.

My project focuses on two distinct aspects of engineering: programming and system integration - which involves the pathfinding algorithm itself - and robotics - which will manifest and reflect the algorithm through physical movement in 3D space.

A* (A Star) Algorithm)

The A star, or simply the A* algorithm is a pathfinding algorithm which aims to find the shortest path from one point to another. Often, this involves the use of graphs (nodes, vertices, and the transition between them). One of the characteristics that distinctify the A star algorithm is that it is an informed search algorithm which uses heuristics to help find the solution. While heuristic is quite a broad and difficult to define/explain concept in computer science, in A star it is actually quite simple: It refers to the estimated distance from any given point to the final destination. Moreover, the algorithm will keep a running record of what nodes it has “visited”, or “can be visited” (nodes which fall into the category of “can be visited” means that it is a neighbor of a node that has been visited). To “visit” a node is essentially analyzing the node’s position in the graph and whether visiting it will get us closer to the destination. By keeping the heuristic distance of any visited node, and looping through each neighboring nodes that gets closer to the destination, the A star algorithm is able to efficiently narrow down the shortest path.

Process and Challenges

Over the course of this project, I created a couple prototypes that served to point out deficiencies and problematic code and hardware. These prototypes helped to flesh out the final product. The process of working on this project was one filled with countless challenges and problems which needed fixing. These ranged from hardware issues such as battery life shortage, lack of grip on tires, imperfect motor precision, as well as too many software and UI  bugs to list. One especially notable challenge I faced was in the consistency of the physical turns within intersections. This was a compound issue caused by imprecisions in the motor and IR sensor. The robot would reach the intersection point at different angles, causing the detection system for their turns to be messed up and often out-of-sync. The motors would often stop too late, causing the car to overshoot the line/intersection point due to momentum. This problem was solved by implementing a re-adjusting function to realign the car back to the grid, in addition to protruding the middle sensors to allow a much more consistent detection of the turn.

Conclusion, Application and Future Outlook

The applications of this technology, in which pathfinding algorithms are used for autonomous and efficient forms of transportations, is certainly almost limitless in what it could achieve in the next few decades. In fact, the implementation of technology such as this one is already starting to become implemented in the upper bounds of industrial manufacturing and delivery, with one example being Amazon’s warehouse management robots which behave in a very similar manner. With time and further development, robots like these will see a drastic increase in usage and versatility. While this project may have only been the tip of the iceberg that is pathfinding technology, this implementation serves to demonstrate possible uses and overall explore the field. However, the project still holds great room for improvement, and further work could be done. This includes the reduction of hardware imperfections, software acceleration, turn speed increase, and many more. All in all however, autonomous navigation is a rapidly growing field of technology that may significantly alter human quality of life in the very near future.