The project was developed as part of the Introduction to Artificial Intelligence (CSC384) at the University of Toronto, Department of Computer Science.
Role
Developer
Tools
Python
Focus Areas
Artificial Intelligence, Heuristics & State-Space Exploration, Heuristic Engineering, Deadlock Detection & Pruning, Cost-Bounded Search, State-Modeling, Algorithm Design
Timeline
February 2025
Overview
Designed and implemented an anytime heuristic search solver for a multi-robot variant of Sokoban under strict time constraints.
Key Contributions
- Implemented an admissible Manhattan distance heuristic for box-to-storage cost estimation.
- Designed an improved heuristic with deadlock detection to prune unsolvable states early and reduce state expansion.
- Built Weighted A* with a custom evaluation function f(n) = g(n) + w * h(n) to balance optimality and runtime performance.
- Developed Iterative Weighted A* and Iterative Greedy Best-First Search to progressively improve solution quality within fixed computation limits.
- Integrated full cycle checking and cost-bounded pruning to improve search efficiency.
- Produced valid solutions within strict runtime limits (≤2 seconds) while progressively improving path optimality as additional time was available.
Technical Skills Demonstrated:
- Heuristic Search (A*, Weighted A*, Greedy Best-First Search)
- State-Space Modeling
- Performance Optimization
- Deadlock Detection & State Pruning
- Cost-Bound Search Optimization
- Algorithm Design
- Python