CS F407: Artificial Intelligence
Group Assignment: Search-Based Problem Solving Agents
Second Semester 2025–2026
Deadline What to Submit Marks Format
Feb 23, 11:59 PM D1: Problem Formulation + Heuristics 30 PDF (5–8 pages)
Mar 3, 11:59 PM D2: Algorithm Analysis 20 PDF (8–12 pages)
Mar 9–14 Mid-Semester Exams – –
Mar 30, 11:59 PM D3: Code + Demo Video 35 GitHub + MP4
Apr 1–10 D4: Written Exam + Viva 15 In-person
Platform: Submit everything on Nalanda. GitHub required only for D3.
Key Point: D1 and D2 are documents only (no code). You implement in D3.
1 What You’re Building
Design and implement an intelligent agent that solves your assigned problem using search algorithms.
# Project Core Challenge Min Level
1 Warehouse Robot Multi-item collection on grid L1
2 N-Puzzle Solver Heuristic design and proof L2
3 Route Planner Multi-criteria optimization L1
4 Timetable Generator Constraint satisfaction as search L1
5 Strategic Puzzle Deadlock detection in puzzles L1
Each project has complexity levels L1–L4. See Appendix B for specifications.
2 D1: Problem Formulation + Heuristics (30 marks)
Deadline: February 23 | Submit: PDF, 5–8 pages | No code
Write a document with four sections:
1. Problem Description (4 marks): Explain your problem in one page. What real-world
scenario does it model? What complexity level (L1–L4) are you attempting? What are the limitations
of your approach?
2. Environment & PEAS (6 marks): Characterize your problem environment. Provide the
PEAS description (Performance measure, Environment, Actuators, Sensors). Classify and justify:
observable? deterministic? episodic? static? discrete? single-agent?
3. Search Formulation (10 marks): Define your search problem formally:
1
CS F407: Artificial Intelligence Group Assignment
State space S with mathematical notation, initial state s0 , goal test as predicate Goal(s),
actions with preconditions/effects, transition model, path cost function g(n), and state
space size analysis |S|.
4. Heuristic Design (10 marks): Design two admissible heuristics. For each: give the
formal definition h(n) = ..., prove admissibility (h(n) ≤ h∗ (n)), analyze consistency, and compare
dominance between your heuristics.
Also submit: Signed Academic Integrity Declaration (Appendix A) as separate PDF.
3 D2: Algorithm Analysis (20 marks)
Deadline: March 3 | Submit: PDF, 8–12 pages | No code
Select four algorithms you will implement: at least two uninformed (from BFS, DFS, DLS,
IDDFS, UCS) and two informed (from Greedy, A*, IDA*). Note: UCS is uninformed; DLS and
IDDFS count separately.
For each algorithm, analyze these four properties specific to your problem:
Property What to Write Marks
Time Complexity Derive Big-O step-by-step using your problem’s b, d, m 6
Space Complexity Analyze frontier and explored set storage 4
Completeness Will it find a solution if one exists? Prove or state conditions. 4
Optimality Will it find the best solution? Prove or give counterexample. 4
End with a summary table comparing all four algorithms. Justify your algorithm choices (2 marks).
4 D3: Implementation + Demo (35 marks)
Deadline: March 30 | Submit: GitHub link + MP4 video
Code (20 marks): Implement all four algorithms and both heuristics. Include visualization of
the search process. Provide clear README with setup instructions. You may use libraries for data
structures (heapq, numpy) but search algorithms must be your own code.
Grading: Correctness (8) + Code quality (4) + Heuristics (4) + Visualization (4).
Demo Video (10 marks): Record 5–7 minute video (1080p, max 500MB). Show: problem intro
(30s), system overview (1min), live runs on easy/medium/hard cases (3min), algorithm comparison
(1.5min). All members must speak.
Empirical Validation (5 marks): Compare your actual results with D2 predictions. Do node
counts match complexity analysis? Explain any differences.
GitHub: Each member should have meaningful commits throughout. Bulk commits near deadline
will raise concerns during viva.
5 D4: Exam + Viva (15 marks)
Schedule: April 1–10 (exact dates on Nalanda)
Written exam (8 marks): 90 minutes, closed-book, questions about your project.
Group viva (7 marks): 15–20 minutes. Any member may be asked about any component.
Individual assessment: D4 grades are individual. If someone clearly didn’t contribute, their
D1–D3 marks may also be adjusted based on viva performance and GitHub history.
2
CS F407: Artificial Intelligence Group Assignment
6 Policies
Late submissions: 10% penalty per day for 3 days, then not accepted. Medical emergencies require
documentation within 24 hours.
Academic integrity: All work must be original. Cite external sources in IEEE format. Plagia-
rism = zero for entire assignment + disciplinary action.
Member dropout: Before Feb 14: recruit replacement or continue as 3. Feb 14–Mar 3: com-
plexity reduced by one level. After Mar 3: case-by-case.
Nalanda down? Screenshot the error, email instructor before deadline, complete submission
when system recovers.
7 Grading Summary
D1 (30 marks) D2 (20 marks)
Problem Description Clear, motivated 4 Algorithm Selection Justified 2
PEAS/Environment Complete 6 Time Complexity Derived 6
State Space Formal 4 Space Complexity Derived 4
Actions/Goals Precise 3 Completeness Proven 4
Path Cost Defined 3 Optimality Proven 4
Heuristics Formal 4
Admissibility Proved 4
Consistency Analyzed 2
D3 (35 marks) D4 (15 marks)
Correctness All work 8 Conceptual Deep 5
Code Quality Documented 4 Analysis Explains 5
Heuristics Implemented 4 Problem Solving Adapts 5
Visualization Clear 4
Demo Professional 10
Empirtic vs Theory Compared 5
3
CS F407: Artificial Intelligence Group Assignment
A Academic Integrity Declaration
ACADEMIC INTEGRITY DECLARATION
CS F407: Artificial Intelligence
Group Assignment, Second Semester 2025–2026
Group Number: Project:
We declare that: (1) this work is entirely our own; (2) we have not shared or received code/content
from other groups; (3) all sources are cited in IEEE format; (4) we understand plagiarism includes
AI-generated content without disclosure; (5) violations result in zero marks and disciplinary action;
(6) each member can explain any component during examination.
S.N. Name ID Signature Date
1
Submit as GroupXX_D1_AcademicIntegrity.pdf with D1.
4
CS F407: Artificial Intelligence Group Assignment
B Project Detailed Specifications
All five projects are designed to have comparable workload and complexity. Choose your complexity
level (L1–L4) based on your group’s ambition.
B.1 Project 1: Intelligent Warehouse Robot Navigation
Domain: Design an agent for a warehouse robot that navigates a grid, collects items, and delivers
them while avoiding obstacles.
Environment: Grid (10x10 to 50x50), static obstacles, multiple items with priorities, energy
constraints.
Complexity Levels:
L1: Single item pickup and delivery, static obstacles
L2: Multiple items with shortest total path
L3: Energy constraints and weighted item priorities
L4: Dynamic obstacles requiring replanning
State: (position, items_collected, energy)
Suggested Heuristics: Manhattan distance to nearest item; MST of remaining items; relaxed
problem ignoring obstacles.
B.2 Project 2: N-Puzzle Solver
Domain: Solve the sliding tile puzzle (8-puzzle, 15-puzzle) with rigorous heuristic analysis.
Environment: Fully observable, deterministic, static. State space: n!/2 reachable configurations.
Complexity Levels:
L1: 8-puzzle with misplaced tiles and Manhattan distance heuristics
L2: 8-puzzle with solvability detection and linear conflict heuristic
L3: 15-puzzle requiring IDA* for memory efficiency
L4: 15-puzzle with pattern database heuristics
Minimum Required: L2 (since 8-puzzle at L1 is a solved textbook example).
Suggested Heuristics: Misplaced tiles; Manhattan distance; Linear conflict; Walking distance;
Pattern databases.
B.3 Project 3: Route Planning System
Domain: Navigation agent for finding optimal routes considering distance, time, or multiple criteria.
Environment: Graph-based road network with weighted edges representing distance/time.
Complexity Levels:
L1: Single source to single destination shortest path
L2: Multi-stop route planning (visiting multiple locations)
L3: Time-dependent edge weights (rush hour traffic)
L4: Multi-objective optimization (minimize both distance and time)
Data Options: BITS Pilani campus map (provided), synthetic grid network, or OpenStreetMap
extract.
Suggested Heuristics: Euclidean distance; Haversine distance for real coordinates; Landmark-
based heuristics.
B.4 Project 4: Timetable Generator
Domain: Generate conflict-free class timetables satisfying various constraints.
Formulation Guidance: Model as search over partial assignments. State = courses scheduled
so far. Action = assign next course to (room, timeslot). Goal = all courses assigned without conflicts.
Complexity Levels:
5
CS F407: Artificial Intelligence Group Assignment
L1: Small: 5 courses, 3 rooms, 5 time slots, hard constraints only
L2: Medium: 15 courses, 5 rooms, 10 slots, instructor availability
L3: Large: 30+ courses with soft constraints (preferences)
L4: Real data: Actual department schedule with all constraints
Hard Constraints: No room double-booking, no instructor conflicts, room capacity.
Soft Constraints: Preferred time slots, minimize gaps, balance daily load.
Suggested Heuristics: Number of unassigned courses; Most constrained variable; Constraint
violation count for relaxed problem.
B.5 Project 5: Strategic Puzzle Agent
Domain: Solve classic puzzles that require planning several moves ahead.
Choose ONE puzzle:
• Sokoban: Push boxes to target locations; boxes only push, never pull
• Rush Hour: Slide cars in a grid to let the red car exit
• Lights Out: Toggle cells to turn off all lights; toggling affects neighbors
• Water Jug: Measure exact quantity using jugs of different capacities
• Tower of Hanoi: Move disk stack to another peg; larger disk never on smaller
Environment: Fully observable, deterministic, but solutions can be very deep.
Complexity Levels:
L1: Small instances solvable with basic BFS/DFS
L2: Medium instances with puzzle-specific heuristics
L3: Large instances requiring IDA* for memory efficiency
L4: Deadlock detection and unsolvability proving
Puzzle-Specific Notes:
• Sokoban: Detect frozen boxes (stuck in corners). State includes box positions.
• Rush Hour: Goal is moving target car to exit. Heuristic: blocking vehicles count.
• Lights Out: Toggle cells to turn all off. Has algebraic solution; compare with search.
• Tower of Hanoi: Classic recursive structure. Prove heuristic admissibility.