Back to Study Feed
osou_maps

ASSIGNMENT-2 Q1 (Course Name- Artificial Intelligence) (Course Code - PGS-AI-205)

Assignment Submission

Course: Artificial Intelligence (Course Code - PGS-AI-205)
Topic: Problem-Solving Techniques in Artificial Intelligence

Introduction

In Artificial Intelligence, problem-solving techniques are systematic methods used by agents to make decisions, navigate environments, and achieve specific target goals. To solve a complex problem, an AI system must represent the environment, process possible actions, and select an optimal or efficient sequence of steps. This paper discusses the foundational frameworks of problem-solving: state-space representation, intelligent agents, uninformed search algorithms, informed search algorithms, and Constraint Satisfaction Problems (CSPs).

1. State-Space Representation

A state-space representation provides a mathematical and structural model to frame a problem as a graph where nodes represent configurations (states) and directed edges represent valid transitions (actions).

Key Components

  • Initial State: The starting configuration of the agent.

  • Actions: The set of valid operations $A(s)$ available in state $s$.

  • Transition Model: A function $\text{Result}(s, a)$ that defines the successor state resulting from executing action $a$ in state $s$.

  • Goal Test: A condition or function checking whether a given state matches the targeted goal.

  • Path Cost: A numerical step cost assigned to moving from one state to another. The total path cost is the cumulative sum of step costs along a trajectory.

Example: The 8-Puzzle Problem

  • State: A $3 \times 3$ grid containing tiles numbered 1 to 8 and one blank space.

  • Initial State: Any arbitrary scrambled arrangement of tiles.

  • Actions: Sliding the blank space {Up, Down, Left, Right}.

  • Goal Test: Tiles arranged sequentially from 1 to 8 with the blank space in the bottom-right corner.

  • Path Cost: Each tile movement incurs a cost of 1.

Practical Applications

  • Autonomous Navigation & GPS: Calculating driving trajectories between coordinates.

  • Robotic Arm Motion: Navigating joint coordinates from a rest state to a target manipulation pose.

2. Intelligent Agents in Problem Solving

An intelligent agent is an autonomous entity that observes its environment using sensors and takes actions using actuators. In problem-solving, an agent follows a goal-directed cycle:

  • Goal Formulation: The agent establishes operational targets based on current performance measures.

  • Problem Formulation: The agent defines the states, actions, and costs necessary to achieve the formulated goal.

  • Search: The agent evaluates its internal state-space model to discover an effective action sequence leading to the goal.

  • Execution: The agent executes the solution sequence step-by-step through its actuators in the real environment.

3. Uninformed Search Algorithms (Blind Search)

Uninformed search algorithms explore the state space using only the problem definition (initial state, available actions, and goal test) without any domain-specific hints about how close a state is to the goal.

Comparison of Algorithms

  • Breadth-First Search (BFS):

    • Strategy: Expands the shallowest unvisited nodes first using a FIFO (First-In-First-Out) queue.

    • Properties: Complete and optimal if all step costs are equal. However, its memory consumption is very high, with a space complexity of $O(b^d)$, where $b$ is the branching factor and $d$ is the goal depth.

    • Application: Social network connections (e.g., finding degrees of separation) and web crawlers.

  • Depth-First Search (DFS):

    • Strategy: Expands the deepest unvisited node first using a LIFO (Last-In-First-Out) stack or recursion.

    • Properties: Not guaranteed to be complete (can get stuck in infinite loops without cycle detection) and not optimal. However, it is memory efficient, with a space complexity of $O(b \cdot m)$, where $m$ is maximum depth.

    • Application: Maze solving, topological sorting, and dependency checking in compilers.

  • Uniform Cost Search (UCS):

    • Strategy: Expands the node with the lowest path cost $g(n)$ accumulated from the start state using a priority queue.

    • Properties: Complete and optimal for arbitrary step costs as long as every step cost is positive.

    • Application: Network routing protocols (such as Dijkstra's algorithm variant) to route packets at minimum cost.

4. Informed (Heuristic) Search Algorithms

Informed search algorithms use domain-specific knowledge provided by a heuristic function $h(n)$, which estimates the remaining cost from state $n$ to the goal.

A. Greedy Best-First Search

Greedy Best-First Search evaluates nodes purely using $f(n) = h(n)$. It expands the node that appears closest to the goal. While computationally fast in many cases, it is neither guaranteed to be complete nor optimal, as it can be guided into dead ends by misleading heuristics.

B. A* Search Algorithm

A* Search combines the path cost accumulated so far with the estimated remaining cost: $f(n) = g(n) + h(n)$, where:

  • $g(n)$: Exact cost incurred to reach node $n$ from the initial state.

  • $h(n)$: Estimated cost from node $n$ to the goal state.

Conditions for Optimality:

  • Admissibility: The heuristic $h(n)$ must never overestimate the actual remaining cost to reach the goal.

  • Consistency (Monotonicity): For every node $n$ and every successor $n'$ generated by action $a$, $h(n) \le c(n, a, n') + h(n')$.

Example & Application

In route planning, $g(n)$ represents the actual driving distance covered, while $h(n)$ is the straight-line (Euclidean) distance to the destination. While Greedy Best-First Search might pick roads pointing directly toward the target regardless of total distance, A* balances actual driving distance with straight-line distance, guaranteeing the shortest overall path. Practical applications include video game NPC movement and navigation engines like Google Maps.

5. Constraint Satisfaction Problems (CSPs)

A Constraint Satisfaction Problem structures search problems by representing states as a set of variables that must satisfy specific conditions or restrictions.

Structure of a CSP

  • Variables ($X$): $\{X_1, X_2, \dots, X_n\}$

  • Domains ($D$): $\{D_1, D_2, \dots, D_n\}$, where each domain contains legal values for its variable.

  • Constraints ($C$): A set of conditions specifying allowed combinations of values across variables.

Solving CSPs Efficiently

  • Backtracking Search: A depth-first approach that assigns values to one variable at a time and backtracks immediately when a constraint is violated.

  • Constraint Propagation (e.g., Arc Consistency / AC-3): Prunes illegal values from variable domains before or during search to reduce the search space.

  • Heuristics:

    • Minimum Remaining Values (MRV): Chooses the variable with the fewest legal options left.

    • Degree Heuristic: Chooses the variable involved in the highest number of constraints with other unassigned variables.

    • Least Constraining Value (LCV): Prefers the value that leaves the most choices open for neighboring variables.

Example: Map Coloring

  • Variables: Geographic regions {WA, NT, SA, Q, NSW, V, T}.

  • Domains: {Red, Green, Blue} for each region.

  • Constraints: Adjacent regions must not share the same color (e.g., $\text{WA} \neq \text{NT}$).

Practical Applications

  • University Exam Timetabling & Scheduling: Assigning time slots and rooms to courses without student conflict.

  • Resource Allocation: Airline crew scheduling and factory task assignment under strict equipment availability constraints.

Conclusion

Problem-solving techniques form the foundation of classical and modern Artificial Intelligence. By choosing the right representation—whether via state-space graphs or constraint networks—and applying targeted search strategies (uninformed, heuristic, or constraint propagation), AI systems can efficiently navigate complex problem domains to deliver optimal, real-world solutions.