The use of 3D data has endless applications, but it would be particularly useful in fields such as digital twin systems, where it can accurately replicate real-world environments. By utilizing Unity, I studied algorithms such as Neural A* and simple waypoint to enable a drone object to navigate a 3D city model with rigid body properties and reach its destination.
A* search algorithm is a graph traversal and path search algorithm.
Unity provides pathfinding module based on A* algorithm. Starting from a
specific node, in my case, from warehouse, it aims to find a path to the
given goal node, in our case, delivery point, having smallest cost.
It is kind of heuristic method. A* expands nodes based on the cost of
getting the node and an estimated cost to reach the goal from that node.
A* expand nodes with the lowest total cost.
I considered using the A* algorithm as a pathfinding method for drones, assuming that the drone has access to map information, specifically the starting and ending points and road network information of the city. However, there are several issues with this assumption. The entire map information of the city may be too heavy for the drone to carry, as it needs to confirm sensor information, self-check problems, and perform transmission and reception roles with the server. Additionally, the A* algorithm uses a somewhat greedy approach that requires scanning through all nodes, which could potentially slow down real-time systems such as drones.
Taking into account these issues, I considered incorporating an algorithm such as neural A*. This is a method proposed by Ryo Yonetani et al. in their paper "Path Planning using Neural A* Search", which uses neural networks to pre-process the calculations needed for pathfinding, resulting in faster speed and greater accuracy than A*. The path is dynamically adjusted, continuously improving the route rather than being statically determined. The first neural network is used to predict the distance between the current node and the goal node, while the second neural network checks the validity of the path. Through this method, the drone can utilize real-time images it collects, enabling the investigation of a pathfinding method for drone delivery that reflects the highly volatile urban environment.
While Neural A* pathfinding is still a heavy method to implement on drones, if a digital twin is created and communication between the drone and server is smooth through the city's CPS network, the pathfinding can be handled by the server in the digital twin and only the motor values of each propeller can be communicated to the actual drone, allowing it to reach the destination with much lighter processing. Given the opportunity for further research, I would like to return to this problem and study the weight reduction of delivery drones using digital twins.