Content
# COS30019 – Tree-Based Search Assignment
**Unit:** COS30019 - Introduction to Artificial Intelligence
**Assignment:** Assignment 2 Part A - Tree Based Search
**Due Date:** 11:59 pm Sunday, 2 November 2025
This project implements six tree-based search algorithms to solve the **Route Finding Problem** in 2D graphs (directed/undirected).
---
## 👥 Team Members (Jupyter Group)
| Member Name | Student ID |
| ---------------------- | ---------- |
| Andrew Teck Foon YII | 104386568 |
| Clement Tiew Song TING | 104384180 |
| Chen Jia KHOO | 102761202 |
| Paing CHAN | 102783895 |
---
## 🛠️ Technology Stack
- **Language:** Python 3.x
- **Dependencies:** `matplotlib` (for visualisation)
---
## 📦 Installation
### Install Dependencies
**For Normal Python:**
```bash
python -m pip install matplotlib
```
**For MSYS2 Python:**
```bash
C:\msys64\usr\bin\pacman.exe -S mingw-w64-x86_64-python-matplotlib --noconfirm
```
---
## 📂 Project Structure
```
├── search.py # Main entry point for running search algorithms
├── utils.py # Helper functions (parsing, heuristics, pathfinding)
├── diagnostics.py # Performance measurement (time & memory)
├── dfs.py # Depth-First Search implementation
├── bfs.py # Breadth-First Search implementation
├── iddfs.py # Iterative Deepening DFS (CUS1)
├── gbfs.py # Greedy Best-First Search implementation
├── aStar.py # A* Search implementation
├── beam.py # Greedy Beam with Limited Discrepancy Backtracking (CUS2)
├── visualise.py # Interactive visualisation tool
├── run_tests.py # Automated test runner for all test files
├── run_comparison.py # Performance comparison across all algorithms
├── generate_random.py # Random test case generator
├── /tests # Test case files (PathFinder-test*.txt)
├── /random # Generated random test cases
├── /visualises # Saved visualisation PDFs (step-by-step in one pdf)
└── README.md # This file
```
---
## 🚀 Usage
### Basic Search
```bash
python search.py <filename> <method> [track]
```
- `<filename>`: Test file path (e.g., `tests/PathFinder-test.txt`)
- `<method>`: Algorithm name (DFS, BFS, CUS1, GBFS, AS, BULB). All are case-insensitive
- `[track]`: Optional - Show step-by-step execution
**Examples:**
```bash
python search.py tests/PathFinder-test.txt DFS
python search.py tests/PathFinder-test.txt A* track
python search.py tests/PathFinder-test.txt CUS1
python search.py tests/PathFinder-test.txt BULB
```
**Output Format:**
```
filename: tests/PathFinder-test.txt
method: DFS
goal: 5
number_of_nodes: 7
path: 2 -> 1 -> 3 -> 5
```
---
## 🤖 Search Algorithms
### Uninformed Search Strategies
| Algorithm | Method Code | Alternate Names | Description |
| --------------------------- | ----------- | --------------- | ----------------------------------------- |
| **Depth-First Search** | `DFS` | - | Explores deepest nodes first (LIFO stack) |
| **Breadth-First Search** | `BFS` | - | Explores level by level (FIFO queue) |
| **Iterative Deepening DFS** | `IDDFS` | `CUS1` | DFS with increasing depth limits |
### Informed Search Strategies
| Algorithm | Method Code | Alternate Names | Description |
| ----------------------------------------------------- | ----------- | --------------- | ------------------------------------- |
| **Greedy Best-First Search** | `GBFS` | - | Uses heuristic h(n) only |
| **A\* Search** | `AS` | `ASTAR`, `A*` | Uses f(n) = g(n) + h(n) |
| **Greedy Beam with Limited Discrepancy Backtracking** | `BULB` | `CUS2`, `BEAM` | Uses h(n), beam width=5 + discrepancy |
**Heuristic Function:** Euclidean distance (Pythagorean theorem) to nearest goal
**Tie-Breaking:** When priorities are equal, nodes are expanded in ascending numerical order
**Chronological Order:** Has priority over tie-breaking in informed search (GBFS, A\*, BULB)
---
## 🧪 Testing & Utilities
### Run All Tests
```bash
python run_tests.py [method]
```
**Examples:**
```bash
python run_tests.py ASTAR # Test A* on all files
python run_tests.py # Test all algorithms
```
### Compare Algorithms
```bash
python run_comparison.py <filename>
```
Shows comparison table with execution time, memory, nodes explored, and path length.
### Generate Random Tests
Generate custom test cases with configurable parameters.
```bash
python generate_random.py [num_nodes] [num_edges] [num_goals]
```
**Parameters:**
- `num_nodes`: Number of nodes (3-10, default: random 5-10)
- `num_edges`: Number of edges (auto-generated if not specified)
- `num_goals`: Number of goal nodes (1 to num_nodes, default: random 1-3)
**Note:** Limits can be adjusted in the source code (search for "CHANGE ME" comments).
**Examples:**
```bash
python generate_random.py 8 12 2
```
Output saved to random folder such as `random/randomX.txt`
---
## 🎨 Visualisation
### Interactive Visualiser
```bash
python visualise.py # Launch GUI (default)
python visualise.py <filename> <method> # Direct mode
```
**Features:**
- **Dual View:** Graph + Complete search tree
- **Controls:** Play/Pause, Speed control, Step navigation, Reset
- **Live Diagnostics:** Execution time & memory with progress bars
- **Coloured Nodes:** Red (expanding), Orange (adding), Yellow (path), Green (explored), Tan (frontier)
- **Heuristic Display:** Shows h(n) or f(n) values beside nodes
- **Save PDF:** Export all steps to `visualises/` folder
**Examples:**
```bash
python visualise.py
python visualise.py tests/PathFinder-test.txt BFS
python visualise.py tests/PathFinder-test.txt A*
```
---
## 📊 Diagnostics
All searches automatically measure execution time (µs/ms/s) and peak memory (B/KiB/MiB/GiB).
View diagnostics with `track` flag:
```bash
python search.py tests/PathFinder-test.txt DFS track
```
---
## 📝 Test File Format
Test files must follow this format:
```
Nodes:
1: (x1,y1)
2: (x2,y2)
...
Edges:
(from,to): cost
(from,to): cost
...
Origin:
start_node_id
Destinations:
goal1; goal2; goal3
```
**Example:**
```
Nodes:
1: (4,1)
2: (2,2)
3: (4,4)
Edges:
(1,2): 5
(2,3): 4
Origin:
1
Destinations:
3
```
---
## 🔑 Key Features
✅ **Six Search Algorithms:** DFS, BFS, IDDFS, GBFS, A\*, BULB
✅ **Tree-Based Search:** Uses branch detection (not graph search)
✅ **Cycle Prevention:** Tracks current path ancestors
✅ **Performance Diagnostics:** Built-in time & memory measurement
✅ **Interactive Visualisation:** Step-by-step algorithm execution
✅ **Automated Testing:** Run all tests with one command
✅ **Performance Comparison:** Compare all algorithms side-by-side
✅ **Random Test Generator:** Create custom test cases
✅ **Directed/Undirected Graphs:** Supports both graph types
✅ **Multiple Destinations:** Find path to any goal node
---
## 🆘 Troubleshooting
### matplotlib Not Found
Install using pip (normal Python) or pacman (MSYS2 Python).
### File Not Found
Run commands from project root directory.
### Visualisation Not Showing
- Check matplotlib backend configuration
- Ensure GUI support is enabled
---
## 📄 License
Self Protected - See LICENSE file
---
## 🎓 Academic Integrity
Submitted for academic evaluation at Swinburne University of Technology.
