Show understanding of how graphs can be used to aid Artificial Intelligence (AI)

Published by Patrick Mutisya · 8 days ago

Cambridge A-Level Computer Science 9618 – 18.1 Artificial Intelligence (AI)

18.1 Artificial Intelligence (AI)

Objective

Show understanding of how graphs can be used to aid Artificial Intelligence (AI).

Why Graphs are Central to AI

  • Many AI problems can be modelled as a set of states and the transitions between them.

  • These states and transitions naturally form a graph \$G = (V, E)\$ where \$V\$ is the set of vertices (states) and \$E\$ is the set of edges (possible actions).

  • Graph‑based representations enable systematic exploration, optimisation and reasoning about solutions.

Graph Representations

Two common ways to store a graph in a computer program are:

RepresentationStructureTypical Use‑case in AI
Adjacency MatrixA two‑dimensional \$|V| \times |V|\$ array \$M\$ where \$M_{ij}=1\$ if an edge \$(i,j)\$ exists, otherwise \$0\$.Dense graphs, quick edge‑existence checks (e.g., board games with many possible moves).
Adjacency ListAn array of lists; each list \$L_i\$ contains all vertices adjacent to vertex \$i\$.Sparse graphs, path‑finding in maps, knowledge‑base navigation.

Search Algorithms on Graphs

AI agents often need to find a path from a start state \$s\$ to a goal state \$g\$. The choice of algorithm depends on the graph’s properties and the problem requirements.

  1. Depth‑First Search (DFS)

    • Explores as far as possible along each branch before backtracking.

    • Space‑efficient (\$O(|V|)\$) but not guaranteed to find the shortest path.

  2. Breadth‑First Search (BFS)

    • Explores all neighbours at the current depth before moving deeper.

    • Guarantees the shortest path in an un‑weighted graph.

    • Uses a queue; worst‑case space \$O(|V|)\$.

  3. Dijkstra’s Algorithm

    • Finds the shortest weighted path from a single source to all other vertices.

    • Requires non‑negative edge weights.

    • Typical implementation uses a priority queue; complexity \$O(|E| \log |V|)\$.

  4. A* Search

    • Combines Dijkstra’s cost‑to‑come \$g(n)\$ with a heuristic estimate \$h(n)\$ of the cost to reach the goal.

    • Evaluation function: \$f(n) = g(n) + h(n)\$

    • If \$h\$ is admissible (never overestimates), A* is optimal.

Heuristic Functions in AI

A heuristic \$h(n)\$ provides domain‑specific knowledge to guide search. Good heuristics are:

  • Admissible: \$h(n) \leq h^*(n)\$, where \$h^*(n)\$ is the true cost to the goal.

  • Consistent (Monotonic): \$h(n) \leq c(n, n') + h(n')\$ for every edge \$(n, n')\$ with cost \$c\$.

Practical AI Applications Using Graphs

ApplicationGraph ModelTypical Algorithm
Path‑finding in games (e.g., navigation meshes)Weighted grid or navigation graph where vertices are walkable positions.A* with Euclidean distance heuristic.
Knowledge representation (semantic networks)Directed graph where concepts are vertices and relationships are labelled edges.DFS/BFS for inference, shortest‑path for similarity measures.
Robot motion planningConfiguration space graph; each vertex is a robot pose.Dijkstra or A* with obstacle‑avoidance heuristics.
Game tree search (e.g., chess)Tree‑like directed graph where each node is a board state.Minimax with alpha‑beta pruning (a specialised depth‑first search).

Comparing Search Strategies

StrategyCompletenessOptimalityTime ComplexitySpace Complexity
DFSNo (may get stuck in loops)No\$O(b^m)\$\$O(bm)\$
BFSYes (if branching factor finite)Yes (un‑weighted)\$O(b^d)\$\$O(b^d)\$
DijkstraYesYes (non‑negative weights)\$O(|E| \log |V|)\$\$O(|V|)\$
A*Yes (if \$h\$ admissible)Yes (if \$h\$ admissible)Depends on \$h\$; worst‑case \$O(b^d)\$\$O(|V|)\$

Suggested Diagram

Suggested diagram: A simple weighted graph illustrating start node \$S\$, goal node \$G\$, edge costs, and the path found by A* compared with the path found by Dijkstra.

Summary

Graphs provide a versatile framework for representing AI problems. By modelling states as vertices and actions as edges, AI algorithms can systematically explore solution spaces. Search techniques such as BFS, DFS, Dijkstra’s algorithm, and A* exploit graph structures to achieve completeness, optimality, or efficiency depending on the problem’s requirements. Understanding how to choose an appropriate representation and algorithm is essential for designing effective AI solutions at A‑Level.