Robot Navigation Assignment (COS30019)

Overview

This repository contains both a CLI and GUI implementation of classic robot navigation problems. A dense grid map defines walls, a start point, and one or more goals. The engine performs systematic search, heuristic search, and hybrid algorithms while optionally streaming every frontier/explored node back to a visualization layer.

Algorithms Implemented

• depth_first_search, breadth_first_search (systematic frontier exploration)
• greedy_best_first_search, a_star_search (heuristic-driven search using Manhattan distance)
• iterative_deepening_search, ida_star_search (depth- and cost-limited iterators)
• multigoal_a_star (chains standard A* to consume each goal sequentially with state restoration) All algorithms report the node count, track the node that reached a goal, and optionally toggle viz callbacks for the GUI.

Environment & Map Format

Environment (see environment.py) parses files with this structure:

1. [rows, cols] – grid size
2. (start_col, start_row) – starting coordinates
3. (goal1_col, goal1_row)|(goal2_col, goal2_row)|... – goal set (can be left blank for single-goal problems) 4+. (wall_col, wall_row, width, height) blocks – each line expands into every covered tile.

Valid successors are returned in the order UP, LEFT, DOWN, RIGHT, and Environment.heuristic picks the closest Manhattan distance to any goal.

Running the CLI

Ensure you have Python 3.9+ and install customtkinter (the GUI lib also depends on it):

pip install customtkinter

Then invoke a search from the root:

python search.py Test/small_map_functional.txt BFS

Swap Test/ files or other methods (DFS, GBFS, A*, CUS1, CUS2, MAS) as needed. Output prints the goal node, node count, and the actions list.

Running the GUI

The map.py module launches a CustomTkinter window (MapApp). It autodetects RobotNav-test.txt in this directory but will accept another map via the Environment constructor. Click the algorithm buttons to animate frontier/explored nodes, and the route is replayed on the grid once a goal is reached. Use the Reset button between runs.

Test Maps

• Test/ contains curated maps for correctness and edge cases (no possible goals, multiple goals, etc.).
• Test/Performance/ provides stress maps (maze-like, wide-open, and symmetry-focused layouts) for measuring algorithmic behavior in harder scenarios.

Visualization Hook

map.py wires a GridFrame (handles cell coloring and animations) to the same search functions used by search.py. The callback _viz_callback accepts keys like frontier/explored to color nodes and optionally introduces animation delay.

Troubleshooting

• If you see FileNotFoundError when running map.py, ensure the chosen map file exists in the working directory or pass a full path when constructing Environment.
• To inspect results programmatically, reuse mapAlgorithms.print_path to map action sequences to actual coordinates.