Heuristic-Based Path Planning with A* for Patient Transportation

This project addresses a real-world resource allocation problem involving the efficient transportation of patients from multiple pickup locations to healthcare centers. The implementation applies heuristic search strategies, focusing particularly on the A* algorithm with multiple admissible heuristics.

Developed in Python, the solution emphasizes algorithmic efficiency, search space optimization, and modular design, providing a realistic simulation of dynamic path planning under constraints such as vehicle capacity and energy consumption.

Problem Description

Given a map in CSV format encoding:

  • Pickup points (patients)
  • Drop-off centers (hospitals)
  • Rechargeable bus stops (parking/energy stations)
  • Energy constraints and capacity limitations

The goal is to compute an optimal route for a medical transport vehicle to:

  • Collect all patients
  • Deliver them to their destinations
  • Recharge when necessary
  • Minimize total travel cost/time

Core Components

1. A Custom Pathfinding Engine*

Implements a custom A* search tailored for the transport problem, supporting three different heuristics:

  • Heuristic 1: Euclidean distance to nearest hospital
  • Heuristic 2: Sum of minimum distances for remaining patients
  • Heuristic 3: Incorporates vehicle energy and patient load state

The class is designed for reuse and extensibility. The algorithm handles state transitions with constraints on:

  • Energy consumption per move
  • Vehicle capacity (number of patients onboard)
  • Map parsing and dynamic environment state

2. Graphical Visualizer (visualizador.py)

A GUI tool based on tkinter that animates the computed path over time, allowing step-by-step review of:

  • Patient pickups and drop-offs
  • Bus energy level
  • Map state evolution

Useful for validation and debugging of the planner’s behavior.

Input / Output

  • Input: CSV file defining the map, where each cell contains a location type (N, C, P, T, etc.)
  • Output: Solution file with the sequence of operations and detailed statistics (time, nodes expanded, cost)

Execution

Run the A* planner:

python3 ASTARTraslados.py mapa.csv <heuristic_number>

Ensure the correct paths are configured within the script before execution.

Educational Goals

This project was developed as part of a university course on heuristic optimization and artificial intelligence. It demonstrates:

  • Effective use of informed search algorithms
  • Trade-offs between admissible heuristics
  • Constraint modeling and state representation
  • Clean Python design for AI agents

Authors

See autores.txt for full author credits.