Pathfinder

Mapping efficient routes between geojson points whilst avoiding obstacles.
Java
MapBox

Pathfinder is a Java project designed to solve a Travelling Salesman Problem (TSP) for drone deliveries. The objective is to determine an optimal route for a drone to visit multiple delivery points while avoiding buildings. Users can either create their own building and delivery point data for use with the project or utilise the provided sample files. This software could be integrated with large datasets, such as Google Open Buildings, to create drone paths that avoid buildings and no-fly zones.



Key Features
- Route Optimisation: The project uses dynamic programming memoisation to optimise the order of delivery point visits, ensuring efficient drone routes.
- Pathfinding: An A* algorithm is employed to determine the paths between delivery points based on the optimised visit order.
- User-Defined Data: Users can provide their own building and delivery point data in GeoJSON and JSON formats, respectively.
- Customisable Output: The output GeoJSON file can be customised in the App class to adjust the format and contents of the output file.
Challenges & Solutions
- Challenge: Limiting Drone Moves for Effective A* Search
To carry out the A* search effectively, the number of possible moves a drone could take needed to be limited.
Solution: A grid was overlaid on the map to confine the drone’s movement. This grid acted as a foundational structure for further calculations, ensuring paths remained computationally feasible. - Challenge: Blocking Grid Areas Representing Obstacles
It was necessary to mark grid areas as inaccessible when they intersected with input polygons (representing buildings or other obstacles). Handling varying coordinates, grid density, and the complexity of shapes efficiently posed a significant challenge.
Solution: A dedicated function was created to calculate where grid lines intersected with buildings. By understanding the grid's density, the space between grid lines, and the length and direction of polygon edges, it was possible to determine blocked areas efficiently. Special considerations were made for the hemisphere (positive or negative latitude/longitude) to ensure calculations were accurate. - Challenge: Optimising Visit Order
Finding the most efficient order to visit multiple points was complex and required a strategy that could handle dynamic inputs.
Solution: Dynamic programming was implemented to determine the optimal order of visits. The algorithm successfully optimised visits for up to 22 points before runtime became impractical, offering a balance between efficiency and performance. - Challenge: Calculating Routes Between Delivery Points
Identifying the shortest paths between points while displaying detailed search features (like explored blocks) in the output added a layer of complexity.
Solution: The A* search algorithm was used to calculate paths between delivery points. Additional functionality was added to output GeoJSON files with details of the search process, enhancing visibility into the algorithm’s operations.
Roadmap
- Smooth Path: Currently, the drone moves directly from the centre of one grid square to the next. Future improvements could smooth the path for more realistic movement.
- Clustering: The current dynamic programming algorithm supports up to 22 delivery points. For larger datasets, K-Means clustering could group nearby points into 22 clusters, after which the DP algorithm could be applied to the clusters.