Pathfinder

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.

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.