Artificial Intelligence

Last Modified: 2/12/2025

1 Uninformed Search

1.1 Agent Design

There are mainly two types of agents: reflex agents and planning agents.

Reflex Agents:
- Choose action based on current percept, and may have memory or a model of the world’s current state.
- Do not consider the future consequences of their actions, just consider how the world IS.
Planning Agents:
- Decisions based on (hypothesized) consequences of actions.
- Must have a model of how the world evolves in response to actions, and formulate a goal (test), consider how the world WOULD BE

1.2 Search Problems

A search problem consists of a state space, a successor function (with actions and costs) and a start space & a goal test. A solution is a sequence of actions (a plan) which transforms the start state to a goal state.

For a search problem, we may need:

State Space Graph: A mathematical representation of a search problem. It consists of nodes (abstarcted world configurations) and arcs (successors/action results). The goal test is a set of goal nodes (maybe only one).
Search Trees: A “what if” tree of plans and their outcomes. Nodes show states, and children correspond to successors.

Search algorithms can be divided into two categories:

Uninformed Search: No additional information about states beyond the definition of the problem.
- Depth-First Search
- Breadth-First Search
- Uniform-Cost Search
Informed Search: Use heuristics to guide the search.
- A* Search

1.2.1 Uniform-cost Search

Uniform-cost search is a variant of Dijkstra’s algorithm. Not inserting all nodes in a graph makes it possible to extend Dijkstra’s algorithm to find the shortest path from a single source to the closest of a set of target nodes on infinite graphs or those too large to represent in memory, which is called uniform-cost search (UCS) in artificial intelligence literature.


106 collapsed lines
1
import java.util.*;
2

3
public class ucs {
4
    private final double[] costTo;
5
    private final int[] parent;
6
    private final PriorityQueue<Integer> pq;
7
    private final boolean[] visited;
8

9
    /**
10
     * A directed edge constructor with a cost.
11
     */
12
    public static class Edge {
13
        int neighbor;
14
        double cost;
15

16
        public Edge(int neighbor, double cost) {
17
            this.neighbor = neighbor;
18
            this.cost = cost;
19
        }
20
    }
21

22
    /**
23
     * Uniform-cost search constructor.
24
     */
25
    public ucs(List<List<Edge>> graph, int startNode) {
26
        int numNodes = graph.size();
27
        costTo = new double[numNodes];
28
        parent = new int[numNodes];
29
        visited = new boolean[numNodes];
30

31
        for (int i = 0; i < numNodes; i++) {
32
            costTo[i] = Double.POSITIVE_INFINITY;
33
            parent[i] = -1;
34
        }
35
        costTo[startNode] = 0.0;
36

37
        pq = new PriorityQueue<>(Comparator.comparingDouble(v -> costTo[v]));
38
        pq.offer(startNode);
39

40
        while (!pq.isEmpty()) {
41
            int currentNode = pq.poll();
42
            visited[currentNode] = true;
43

44
            if (costTo[currentNode] == Double.POSITIVE_INFINITY) continue;
45

46
            for (Edge edge : graph.get(currentNode)) {
47
                relax(currentNode, edge.neighbor, edge.cost);
48
            }
49
        }
50
    }
51

52
    /**
53
     * Relaxation of an edge.
54
     *
55
     * @param u the source node
56
     * @param v the target node
57
     * @param cost the cost of the edge
58
     */
59
    private void relax(int u, int v, double cost) {
60
        if (costTo[v] > costTo[u] + cost) {
61
            costTo[v] = costTo[u] + cost;
62
            parent[v] = u;
63
            pq.offer(v);
64
        }
65
    }
66

67
    /**
68
     * Get the cost to a node.
69
     *
70
     * @param node the target node
71
     * @return the cost to the target node
72
     */
73
    public double getCostTo(int node) {
74
        return costTo[node];
75
    }
76

77
    /**
78
     * Check if a path exists to a node.
79
     *
80
     * @param node the target node
81
     * @return true if a path exists, false otherwise
82
     */
83
    public boolean hasPathTo(int node) {
84
        return costTo[node] < Double.POSITIVE_INFINITY;
85
    }
86

87
    /**
88
     * Get the path to a node.
89
     *
90
     * @param targetNode the target node
91
     * @return the path to the target node
92
     */
93
    public List<Integer> getPathTo(int targetNode) {
94
        if (!hasPathTo(targetNode)) {
95
            return null;
96
        }
97

98
        List<Integer> path = new ArrayList<>();
99
        for (int v = targetNode; v != -1; v = parent[v]) {
100
            path.add(v);
101
        }
102

103
        Collections.reverse(path);
104
        return path;
105
    }
106
}


40 collapsed lines
1
#ifndef UCS_H
2
#define UCS_H
3

4
#include <vector>
5
#include <queue>
6
#include <functional>
7
#include <limits>
8
#include <cmath>
9
#include <algorithm>
10

11
namespace ucs {
12

13
    struct Node {
14
        int neighbor;
15
        double cost;
16

17
        Node(const int neighbor, const double cost) : neighbor(neighbor), cost(cost) {}
18
    };
19

20
    class UniformCostSearch {
21
    private:
22
        std::vector<double> costTo;
23
        std::vector<int> parent;
24
        std::vector<bool> visited;
25
        std::priority_queue<int, std::vector<int>, std::function<bool(int, int)>> pq;
26
        const std::vector<std::vector<Node>>& adj;
27

28
        void relax(int u, int v, double cost);
29

30
    public:
31
        UniformCostSearch(const std::vector<std::vector<Node>>& graph, int startNode);
32

33
        [[nodiscard]] double getCostTo(int node) const;
34
        [[nodiscard]] bool hasPathTo(int node) const;
35
        [[nodiscard]] std::vector<int> getPathTo(int targetNode) const;
36
    };
37

38
} // namespace ucs
39

40
#endif //UCS_H


81 collapsed lines
1
#include "ucs.h"
2

3
namespace ucs {
4

5
    UniformCostSearch::UniformCostSearch(const std::vector<std::vector<Node>>& graph, const int startNode)
6
        : costTo(graph.size(), std::numeric_limits<double>::infinity()),
7
          parent(graph.size(), -1),
8
          visited(graph.size(), false),
9
          pq([this](const int u, const int v) { return costTo[u] > costTo[v]; }),
10
          adj(graph)
11
    {
12
        costTo[startNode] = 0.0;
13
        pq.push(startNode);
14

15
        while (!pq.empty()) {
16
            const int currentNode = pq.top();
17
            pq.pop();
18
            visited[currentNode] = true;
19

20
            if (costTo[currentNode] == std::numeric_limits<double>::infinity()) continue;
21

22
            for (const auto& edge : adj[currentNode]) {
23
                relax(currentNode, edge.neighbor, edge.cost);
24
            }
25
        }
26
    }
27

28
    /**
29
     * Relaxation of an edge.
30
     *
31
     * @param u the source node
32
     * @param v the target node
33
     * @param cost the cost of the edge
34
     */
35
    void UniformCostSearch::relax(const int u, const int v, const double cost) {
36
        if (costTo[v] > costTo[u] + cost) {
37
            costTo[v] = costTo[u] + cost;
38
            parent[v] = u;
39
            pq.push(v);
40
        }
41
    }
42

43
    /**
44
     * Get the cost to a node.
45
     *
46
     * @param node the target node
47
     * @return the cost to the target node
48
     */
49
    double UniformCostSearch::getCostTo(const int node) const {
50
        return costTo[node];
51
    }
52

53
    /**
54
     * Check if a path exists to a node.
55
     *
56
     * @param node the target node
57
     * @return true if a path exists, false otherwise
58
     */
59
    bool UniformCostSearch::hasPathTo(const int node) const {
60
        return costTo[node] < std::numeric_limits<double>::infinity();
61
    }
62

63
    /**
64
     * Get the path to a node.
65
     *
66
     * @param targetNode the target node
67
     * @return the path to the target node
68
     */
69
    std::vector<int> UniformCostSearch::getPathTo(const int targetNode) const {
70
        if (!hasPathTo(targetNode)) {
71
            return {};
72
        }
73
        std::vector<int> path;
74
        for (int v = targetNode; v != -1; v = parent[v]) {
75
            path.push_back(v);
76
        }
77
        std::ranges::reverse(path);
78
        return path;
79
    }
80

81
} // namespace ucs


56 collapsed lines
1
import heapq
2

3
class Node:
4
    def __init__(self, neighbor, cost):
5
        '''A directed edge constructor with a cost.'''
6
        self.neighbor = neighbor
7
        self.cost = cost
8

9
class UniformCostSearch:
10
    def __init__(self, graph, start_node):
11
        '''Uniform-cost search constructor.'''
12
        self.cost_to = [float('inf')] * len(graph)
13
        self.parent = [-1] * len(graph)
14
        self.visited = [False] * len(graph)
15
        self.pq = [(0, start_node)]
16
        self.adj = graph
17

18
        self.cost_to[start_node] = 0.0
19

20
        while self.pq:
21
            current_cost, current_node = heapq.heappop(self.pq)
22
            if self.visited[current_node]:
23
                continue
24
            self.visited[current_node] = True
25

26
            if self.cost_to[current_node] == float('inf'):
27
                continue
28

29
            for edge in self.adj[current_node]:
30
                self.relax(current_node, edge.neighbor, edge.cost)
31

32
    def relax(self, u, v, cost):
33
        '''Relaxation of an edge.'''
34
        if self.cost_to[v] > self.cost_to[u] + cost:
35
            self.cost_to[v] = self.cost_to[u] + cost
36
            self.parent[v] = u
37
            heapq.heappush(self.pq, (self.cost_to[v], v))
38

39
    def get_cost_to(self, node):
40
        '''Get the cost to a node.'''
41
        return self.cost_to[node]
42

43
    def has_path_to(self, node):
44
        '''Check if a path exists to a node.'''
45
        return self.cost_to[node] < float('inf')
46

47
    def get_path_to(self, target_node):
48
        '''Get the path to a node.'''
49
        if not self.has_path_to(target_node):
50
            return None
51
        path = []
52
        v = target_node
53
        while v != -1:
54
            path.append(v)
55
            v = self.parent[v]
56
        return path[::-1]

1.2.2 A* Search

A* search is a kind of heuristic search algorithms. It combines uniform-cost search and greedy algorithm.

$g\left(n\right)$ : The cost from the start to reach the node $n$ , which uniform-cost search relies on.
$h\left(n\right)$ : An estimate of the cost from node $n$ to the goal, which greedy algorithm relies on.

The A* search algorithm uses the following formula to calculate the cost of a node:

f\left(n\right) = g\left(n\right) + h\left(n\right)

Admissible heuristics: A heuristic $h$ is admissible (optimistic) if:

h\left(n\right) \leq h^*\left(n\right)

where $h^*\left(n\right)$ is the true cost to reach the goal from node $n$ . The admissible heuristic guarantees that A* will never stop exploring a path that could lead to a better solution. With inadmissible heuristics, A* may think a node is “too expensive” and stop exploring it, even if that node is actually on the optimal path.

For admissible heuristics, there are some methods for calculating $h\left(n\right)$ :

Manhattan Distance: The sum of the absolute differences of the $x$ and $y$ coordinates.

h\left(n\right) = \left|x_{\text{goal}} - x_{\text{current}}\right| + \left|y_{\text{goal}} - y_{\text{current}}\right|

Euclidean Distance: The straight-line distance between two points.

h\left(n\right) = \sqrt{\left(x_{\text{goal}} - x_{\text{current}}\right)^2 + \left(y_{\text{goal}} - y_{\text{current}}\right)^2}

Chebyshev Distance: The maximum of the absolute differences of the $x$ and $y$ coordinates.

h\left(n\right) = \max\left(\left|x_{\text{goal}} - x_{\text{current}}\right|, \left|y_{\text{goal}} - y_{\text{current}}\right|\right)

Octile Distance: The diagonal distance between two points.

h\left(n\right) = \left(\sqrt{2} - 1\right) \cdot \min\left(\left|x_{\text{goal}} - x_{\text{current}}\right|, \left|y_{\text{goal}} - y_{\text{current}}\right|\right) + \max\left(\left|x_{\text{goal}} - x_{\text{current}}\right|, \left|y_{\text{goal}} - y_{\text{current}}\right|\right)

Zero Heuristic: The heuristic that always returns zero (which is the same as uniform-cost search).

1
import java.util.*;
2

3
public class AStarSearch {
4

5
    public static class AStar {
6
        private final int[][] grid;
7
        private final Node[][] nodes;
8
        private final int rows;
9
        private final int cols;
10

11
        /**
12
         * Constructs an AStar instance for a given grid.
13
         * The grid is a 2D array where 0 indicates a walkable cell and 1 indicates an obstacle.
14
         *
15
         * @param grid The grid for the A* search.
16
         */
17
        public AStar(int[][] grid) {
18
            this.grid = grid;
19
            this.rows = grid.length;
20
            this.cols = grid[0].length;
21
            this.nodes = new Node[rows][cols];
22

23
            for (int y = 0; y < rows; y++) {
24
                for (int x = 0; x < cols; x++) {
25
                    nodes[y][x] = new Node(x, y);
26
                }
27
            }
28
        }
29

30
        /**
31
         * Resets all nodes to their initial state.
32
         * This is useful when performing multiple searches on the same grid.
33
         */
34
        private void resetNodes() {
35
            for (int y = 0; y < rows; y++) {
36
                for (int x = 0; x < cols; x++) {
37
                    Node n = nodes[y][x];
38
                    n.g = Double.POSITIVE_INFINITY;
39
                    n.h = 0;
40
                    n.f = Double.POSITIVE_INFINITY;
41
                    n.parent = null;
42
                }
43
            }
44
        }
45

46
        /**
47
         * Finds a path from the start cell to the goal cell using the A* search
48
         * algorithm.
49
         *
50
         * @param startX The x-coordinate of the start cell.
51
         * @param startY The y-coordinate of the start cell.
52
         * @param goalX  The x-coordinate of the goal cell.
53
         * @param goalY  The y-coordinate of the goal cell.
54
         * @return A list of nodes representing the path (including start and goal),
55
         *         or null if no path is found.
56
         */
57
        public List<Node> findPath(int startX, int startY, int goalX, int goalY) {
58
            resetNodes();
59

60
            Node start = nodes[startY][startX];
61
            Node goal = nodes[goalY][goalX];
62

63
            /* Open list to hold nodes to be evaluated. */
64
            PriorityQueue<Node> openList = new PriorityQueue<>();
65
            /* Closed list to mark visited cells. */
66
            boolean[][] closed = new boolean[rows][cols];
67

68
            start.g = 0;
69
            start.h = heuristic(start, goal);
70
            start.f = start.g + start.h;
71
            openList.add(start);
72

73
            while (!openList.isEmpty()) {
74
                Node current = openList.poll();
75

76
                // If the goal is reached, reconstruct and return the path.
77
                if (current.equals(goal)) {
78
                    return reconstructPath(current);
79
                }
80

81
                closed[current.y][current.x] = true;
82

83
                for (Node neighbor : getNeighbors(current)) {
84
                    if (closed[neighbor.y][neighbor.x]) {
85
                        continue;
86
                    }
87

88
                    double tentativeG = current.g + 1; // Cost to move to the neighbor.
89

90
                    // If a shorter path to neighbor is found, update its cost and parent.
91
                    if (tentativeG < neighbor.g) {
92
                        neighbor.parent = current;
93
                        neighbor.g = tentativeG;
94
                        neighbor.h = heuristic(neighbor, goal);
95
                        neighbor.f = neighbor.g + neighbor.h;
96

97
                        // Add neighbor to open list if it's not already there.
98
                        if (!openList.contains(neighbor)) {
99
                            openList.add(neighbor);
100
                        }
101
                    }
102
                }
103
            }
104

105
            return null;
106
        }
107

108
        /**
109
         * Reconstructs the path from the goal node back to the start node.
110
         *
111
         * @param node The goal node.
112
         * @return A list of nodes representing the path from start to goal.
113
         */
114
        private List<Node> reconstructPath(Node node) {
115
            List<Node> path = new ArrayList<>();
116
            while (node != null) {
117
                path.add(node);
118
                node = node.parent;
119
            }
120
            Collections.reverse(path);
121
            return path;
122
        }
123

124
        /**
125
         * The Manhattan distance heuristic function.
126
         *
127
         * @param a The current node.
128
         * @param b The goal node.
129
         * @return The Manhattan distance between node a and node b.
130
         */
131
        private double heuristic(Node a, Node b) {
132
            return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
133
        }
134

135
        /**
136
         * Retrieves valid neighboring nodes (up, down, left, right) that
137
         * are walkable.
138
         *
139
         * @param node The current node.
140
         * @return A list of valid neighbor nodes.
141
         */
142
        private List<Node> getNeighbors(Node node) {
143
            List<Node> neighbors = new ArrayList<>();
144
            int x = node.x;
145
            int y = node.y;
146
            int[][] directions = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
147

148
            for (int[] d : directions) {
149
                int newX = x + d[0];
150
                int newY = y + d[1];
151

152
                // Ensure new coordinates are within the grid boundaries.
153
                if (newX >= 0 && newX < cols && newY >= 0 && newY < rows) {
154
                    // Check if the cell is walkable.
155
                    if (grid[newY][newX] == 0) {
156
                        neighbors.add(nodes[newY][newX]);
157
                    }
158
                }
159
            }
160
            return neighbors;
161
        }
162

163
        /**
164
         * Represents a node (cell) in the grid.
165
         */
166
        public static class Node implements Comparable<Node> {
167
            public final int x, y;  // Grid coordinates.
168
            public double g;        // Cost from the start node.
169
            public double h;        // Heuristic cost to the goal.
170
            public double f;        // Total cost (g + h).
171
            public Node parent;     // Reference to the parent node for path reconstruction.
172

173
            public Node(int x, int y) {
174
                this.x = x;
175
                this.y = y;
176
                this.g = Double.POSITIVE_INFINITY;
177
                this.h = 0;
178
                this.f = Double.POSITIVE_INFINITY;
179
                this.parent = null;
180
            }
181

182
            @Override
183
            public int compareTo(Node other) {
184
                return Double.compare(this.f, other.f);
185
            }
186

187
            @Override
188
            public boolean equals(Object obj) {
189
                if (this == obj) return true;
190
                if (obj == null || getClass() != obj.getClass()) return false;
191
                Node other = (Node) obj;
192
                return x == other.x && y == other.y;
193
            }
194

195
            @Override
196
            public int hashCode() {
197
                return Objects.hash(x, y);
198
            }
199
        }
200
    }
201

202
    public static void main(String[] args) {
203
        int[][] grid = {
204
                { 0, 0, 0, 0, 0 },
205
                { 0, 1, 1, 1, 0 },
206
                { 0, 0, 0, 1, 0 },
207
                { 0, 1, 0, 0, 0 },
208
                { 0, 0, 0, 1, 0 }
209
        };
210

211
        AStar aStar = new AStar(grid);
212
        List<AStar.Node> path = aStar.findPath(0, 0, 4, 4);
213

214
        if (path != null) {
215
            System.out.println("Path found:");
216
            for (AStar.Node node : path) {
217
                System.out.println("(" + node.x + ", " + node.y + ")");
218
            }
219
        } else {
220
            System.out.println("No path found.");
221
        }
222
    }
223
}