AIF: Implementation of search algorithms

This project implements and evaluates the performance of three foundational search algorithms: Depth-First Search (DFS), Breadth-First Search (BFS), and the informed A* search to solve a pathfinding problem on a non-uniform cost grid. The core task is modeling the path of a drilling robot, simulated here for mineral extraction, where a state is defined by its spatial coordinates and its orientation.

This project was developed as the first laboratory assignment for the course Artificial Intelligence Fundamentals (P4251101) at Universidade de Santiago de Compostela.

Core Features

• State Space: Solves pathfinding on an $N \times M$ cost grid, with different costs for forward movement (based on terrain) and turning (fixed cost).
• Map Flexibility: Supports loading maps from external text files or generating randomized maps for performance testing.
• Performance Evaluation: Includes a batch simulation mode to compare algorithm performance (path cost, depth, nodes explored/frontier size) across varying, randomly generated $M \times M$ map sizes.
• Visualization: Provides detailed execution traces and interactive search tree visualizations for analysis.

Group Members

• Jose Carlos Bordon Maldonado
• Andrea Real Blanco
• Raúl Trillo Martínez

⚙️ Installation

1. Clone this repository or download it as a ZIP:

   git clone https://github.com/arebla/AIF-search-algorithms.git
   cd AIF-search-algorithms

2. (Optional but recommended) Create a virtual environment:

   python -m venv venv
   source venv/bin/activate   # Linux / Mac
   venv\Scripts\activate      # Windows

3. Install dependencies:

   pip install -r requirements.txt

🤖 Usage

The project is executed via the main.py script, which provides a command-line interface (CLI) menu.

1. Run the program:

   python main.py

2. The main menu (Pathfinder Menu) has three modes:

   1. Generate new map: Creates a random map and allows single-run solving.
   2. Load existing map and solve: Requires a map filename (e.g., maps/my_map.txt). Prompts for algorithm choice and visualization display.
   3. Run batch simulation: Executes an automated performance comparison across all three algorithms on multiple random maps (default sizes: $3 \times 3$, $5 \times 5$, $7 \times 7$, $9 \times 9$).

3. Output. The program provides comprehensive results:

   • Execution Trace: Detailed logs of nodes, operators, and costs.
   • Final Metrics: Number of explored nodes, frontier size, total cost, and path depth.
   • Visualizations (if enabled): map path on the grid, search tree (static, Matplotlib), search tree (interactive HTML with Pyvis, saved to the project directory).