Academic implementations of classical artificial intelligence algorithms developed for AI-2002 at FAST National University of Computer and Emerging Sciences. This repository demonstrates foundational AI concepts through algorithmic implementations of search strategies, optimization techniques, and constraint satisfaction problems.
All implementations are built from first principles without reliance on external AI/ML libraries, emphasizing algorithmic understanding and problem-solving methodologies that form the theoretical foundation of artificial intelligence.
Course: AI-2002 - Artificial Intelligence
Institution: FAST National University of Computer and Emerging Sciences
Academic Period: Spring 2025
This repository represents coursework completed for a university-level artificial intelligence course, with emphasis on:
- Algorithmic Foundations: Core AI algorithms implemented from scratch
- Problem Formulation: Translating real-world problems into formal AI search and optimization tasks
- Complexity Analysis: Understanding time and space trade-offs in algorithm design
- Comparative Analysis: Evaluating multiple approaches to the same problem class
The work prioritizes conceptual clarity and correctness over performance optimization, serving as a demonstration of fundamental AI principles rather than production-ready systems.
ai-traditional-search-algorithms/
├── assignment1_multi_robot_pathfinding/ # Informed search in dynamic environments
├── assignment2_search_optimization/ # Local search and evolutionary algorithms
├── assignment3_constraint_satisfaction/ # CSP techniques and game theory
Each assignment directory contains standalone implementations with documentation, test data, and results.
A* Algorithm: Optimal pathfinding using admissible heuristics. Implemented with temporal extension for dynamic environment navigation, demonstrating state-space expansion in 4D (x, y, time, agent_id).
Key Concepts:
- Priority queue-based frontier management
- Manhattan distance heuristic for grid navigation
- Admissibility and consistency in heuristic design
- Temporal collision detection in multi-agent systems
Applications: Multi-robot pathfinding with dynamic obstacles
Local Beam Search: Parallel hill-climbing maintaining k best states simultaneously. Implemented for graph coloring with custom heuristic functions balancing multiple competing objectives.
Key Concepts:
- Successor generation strategies
- Multi-objective heuristic design
- Escape from local optima via beam diversity
- Balance between exploration and exploitation
Applications: Graph coloring with extended constraints
Depth-First Search (DFS): Recursive graph traversal for pattern detection and subgraph classification.
Breadth-First Search (BFS): Level-order exploration for shortest path discovery and graph analysis.
Key Concepts:
- State space representation
- Systematic exploration strategies
- Completeness and optimality guarantees
- Graph traversal complexity analysis
Applications: Subgraph pattern detection, course swap optimization
Genetic Algorithm: Population-based stochastic optimization with selection, crossover, and mutation operators. Implemented for multi-constraint optimization with domain-specific repair mechanisms.
Key Concepts:
- Chromosome encoding and representation
- Fitness function design for multi-objective problems
- Tournament selection for diversity preservation
- Crossover and mutation operator design
- Constraint handling and repair strategies
- Elitism and convergence criteria
Applications: Shelf allocation optimization with 10+ constraints
Parameters:
- Population size: 100
- Generations: 500
- Crossover rate: 0.8
- Mutation rate: 0.15
- Selection: Tournament (k=5)
Backtracking Search: Systematic assignment with intelligent backtracking for constraint satisfaction. Implemented with modern CSP techniques including forward checking and arc consistency.
Key Concepts:
- Variable and domain representation
- Constraint propagation mechanisms
- Backjumping for efficiency
- Variable ordering heuristics (MRV, degree)
- Value ordering heuristics (LCV)
Forward Checking: Eagerly detect constraint violations by maintaining consistency after each assignment, pruning domains of future variables.
Arc Consistency (AC-3): Enforce local consistency between pairs of variables, reducing domain sizes before and during search.
Applications: Ultimate Tic-Tac-Toe game state management
Minimax with Alpha-Beta Pruning: Optimal decision-making in adversarial settings with branch elimination for computational efficiency.
Key Concepts:
- Game tree representation
- Minimax principle for zero-sum games
- Alpha-beta pruning for search space reduction
- Evaluation functions for non-terminal states
- Iterative deepening for time-bounded decisions
- Transposition tables for state memoization
Performance: ~90% node pruning, 10× speedup over vanilla minimax
Hybrid Approach: Combined CSP constraint checking with minimax evaluation for Ultimate Tic-Tac-Toe, demonstrating integration of multiple AI paradigms.
Applications: AI agent for Ultimate Tic-Tac-Toe
Domain: Robotics, autonomous navigation, warehouse automation
Challenges:
- Dynamic obstacle prediction
- Decentralized planning without global knowledge
- Temporal collision avoidance
- Scalability to large state spaces (1000×1000 grids)
Techniques: Temporal A*, collision detection, heuristic design
Domain: Register allocation, scheduling, frequency assignment
Challenges:
- NP-complete optimization
- Multiple competing constraints
- Balance between optimality and computational feasibility
Techniques: Local beam search, constraint-aware heuristics
Domain: Operations research, logistics, resource allocation
Challenges:
- Large solution spaces
- Multiple hard and soft constraints
- Non-linear objective functions
Techniques: Genetic algorithms, constraint handling, fitness design
Domain: Strategic decision-making, adversarial planning
Challenges:
- Exponential game tree growth
- Real-time decision requirements
- Optimal move selection under uncertainty
Techniques: Minimax, alpha-beta pruning, CSP integration
No External AI Libraries: All algorithms implemented from scratch using Python standard library and NumPy for numerical operations only.
Modular Design: Separation of concerns with distinct modules for:
- State representation and manipulation
- Search algorithm logic
- Heuristic and evaluation functions
- Visualization and I/O
Generic Implementations: Reusable code structures applicable beyond specific problem instances.
- Priority Queues: Binary heaps for A* frontier management
- Hash Tables: Explored state tracking and memoization
- Graphs: Adjacency lists and matrices for graph problems
- Trees: Game tree representation for minimax search
Time Complexity:
- A* pathfinding: O(b^d) where b is branching factor, d is solution depth
- Local beam search: O(k × g × s) for k beams, g generations, s successors
- Genetic algorithm: O(p × g × f) for p population, g generations, f fitness evaluation
- Minimax with alpha-beta: O(b^(d/2)) optimal pruning
Space Complexity:
- Temporal A*: O(N × M × T) for grid size N×M, time horizon T
- Beam search: O(k × |S|) for k beams, state size S
- Backtracking CSP: O(d) for maximum depth d
Each assignment is self-contained with:
- Source Code: Core implementation files
- Documentation: Algorithm explanations and usage instructions
- Test Data: Sample inputs and benchmark datasets
- Results: Output files, visualizations, performance metrics
Detailed technical documentation, algorithm explanations, and usage instructions are provided in individual assignment README files.
numpy>=1.24.0 # Numerical computations only
matplotlib>=3.7.0 # Visualization
pygame>=2.5.0 # Real-time rendering
pandas>=2.0.0 # Tabular data handling
openpyxl>=3.1.0 # Excel output generation
# Clone repository
git clone https://github.com/yourusername/ai-traditional-search-algorithms.git
cd ai-traditional-search-algorithms
# Install dependencies
pip install -r requirements.txtThis repository contains original work completed individually for academic coursework. All implementations adhere to course guidelines:
- No use of AI/ML frameworks or libraries
- No pre-built search or optimization packages
- All algorithms implemented from foundational concepts
- Proper documentation and code commentary
Code is shared publicly for educational and portfolio purposes following course completion.
Understanding when to apply specific algorithms based on problem characteristics:
- Complete vs. Optimal: Trade-offs between solution guarantees
- Time vs. Space: Memory-bounded vs. time-bounded search
- Deterministic vs. Stochastic: Guaranteed solutions vs. probabilistic optimization
Translating informal problem descriptions into formal AI representations:
- State space definition and representation
- Action/operator specification
- Goal formulation and termination criteria
- Constraint identification and encoding
Developing effective evaluation functions:
- Admissibility and consistency requirements
- Domain-specific knowledge incorporation
- Multi-objective balancing in composite heuristics
Practical considerations in algorithm implementation:
- Completeness vs. efficiency
- Optimality vs. computational cost
- Generality vs. domain-specific optimization
Potential enhancements to explore advanced AI concepts:
- Probabilistic Planning: Uncertainty handling in pathfinding
- Online Learning: Adaptive heuristics from experience
- Parallel Search: Multi-threaded algorithm implementations
- Approximate Methods: Anytime algorithms for time-bounded scenarios
- Hybrid Approaches: Combining multiple AI paradigms
- Russell, S., & Norvig, P. Artificial Intelligence: A Modern Approach (4th ed.)
- Poole, D., & Mackworth, A. Artificial Intelligence: Foundations of Computational Agents
- Hart, P., Nilsson, N., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths
- Dechter, R. Constraint Processing
- Goldberg, D. Genetic Algorithms in Search, Optimization, and Machine Learning
Hafsa Imtiaz
LinkedIn: www.linkedin.com/in/hafsa-imtiaz-cs
Note: This repository contains academic coursework for educational purposes. Implementations prioritize algorithmic clarity and conceptual demonstration over production optimization.