1. Introduction to Search Problems

1.1 Definition and Core Concepts of a Search Problem

1.1.1 Goal-Based Agents and Systematic Exploration

In Artificial Intelligence, search is the systematic process of exploring possible sequences of choices to navigate from an initial state to a desired goal state. Rather than acting blindly or attempting haphazard trial-and-error, an intelligent agent formulates its task as a search problem to identify the most efficient sequence of actions before executing them.

Key real-world applications of search problems introduced in the course include:

• Grocery Shopping: Identifying the shortest, most efficient walking path through store aisles to collect required items while avoiding unnecessary aisles.
• Route Planning: Computing optimal navigational routes in apps like Google Maps based on distance, travel time, or fuel consumption.
• Game Playing: Determining legal tactical moves in games like chess to reach a winning board configuration.
• Maze Solving: Navigating an agent from a starting entry point through passages to an exit.

1.1.2 The 5 Core Components of a Search Problem

A search problem is formally specified by five foundational components:

1. Initial State ($s_0$): The starting condition or position where the agent begins its search.

   • Example (Maze): The entry location of the agent.
   • Example (Chess): The standard opening board configuration.
   • Example (Route Planning): The agent's current geographical location.

2. Actions / Successor Function ($Actions(s) $): The set of all legal moves or decisions available to the agent when in a given state $s$.

   • Example (Maze): Legal directional steps such as $Actions(s) \in {\text{Up}, \text{Down}, \text{Left}, \text{Right}}$.
   • Example (Chess): Moving a pawn, capturing a piece, or castling according to rules.
   • Example (Route Planning): Choosing which road to take or which direction to turn at an intersection.

3. Transition Model ($Result(s, a) $): A deterministic function that maps state $s$ and action $a$ to the resulting state $s'$.

   • Example (Maze): If the agent is at coordinates $(x, y)$ and takes action $\text{Right}$, the transition model yields state $(x+1, y)$.
   • Example (Chess): Board layout resulting from executing a selected legal move.

4. Goal Test Function ($IsGoal(s) $): A boolean function that evaluates whether a given state $s$ satisfies the problem's objective, indicating when the search process should terminate.

   • Example (Maze): Checking whether the current position equals the exit coordinates.
   • Example (Puzzle): Evaluating whether the current tile configuration matches the target solved pattern.
   • Example (Route Planning): Checking whether all required destination towns have been visited.

5. Path Cost Function ($C(p) $): A numeric scoring function that assigns a cumulative cost to a sequence of actions or state transitions along path $p$, allowing the agent to evaluate and compare alternative solutions to find the optimal route.

   • Example (Maze): Total physical distance or step count to reach the exit.
   • Example (Chess): Total number of moves required to achieve checkmate.
   • Example (Route Planning): Distance traveled, time spent, or energy/fuel consumed.

1.1.3 State Space and Problem Domain

The Initial State, Actions, and Transition Model together implicitly define the state space of a search problem.

The state space represents the complete universe of all valid states or configurations that an agent can potentially occupy during search. The precise features included in a state definition depend strictly on the problem formulation:

• Maze: Set of all valid physical coordinates $(x, y)$ inside the maze grid.
• Chess: Set of all legal, reachable piece configurations on the $8 \times 8$ board.
• Route Planning: The agent's position on the road network, target destinations, and history of route segments traveled.

1.2 Concrete Example: Road Trip Route-Finding Problem

1.2.1 Problem Formulation using the 5-Tuple

To illustrate how a real-world scenario is formulated as a formal search problem, consider planning a road trip to visit a specific set of towns efficiently without wasting fuel or sitting in traffic.

The road trip search problem is structured as follows:

• Initial State ($s_0$): The starting location of the vehicle.
• Actions ($Actions(s) $): The choice of road segments available at the current intersection.
• Transition Model ($Result(s, a) $): The updated geographical position and travel state after driving down the chosen road.
• Goal Test ($IsGoal(s) $): Evaluating whether the vehicle has successfully visited all target towns on the itinerary.
• Path Cost Function ($C(p) $): Total cumulative distance traveled, driving time, or fuel consumed.

1.2.2 Path Cost Optimization and Resource Trade-offs

Let path $p$ be defined as a sequence of states and actions:

$$p = (s_0, a_1, s_1, a_2, s_2, \dots, a_k, s_k)$$

where $c(s_{i-1}, a_i, s_i)$ denotes the step cost of taking action $a_i$ from state $s_{i-1}$ to state $s_i$.

The multi-step derivation for the total path cost $C(p)$ is expressed as:

$$\begin{alignat*}{4} && C(p) &= \sum\limits_{i=1}^{k} c(s_{i-1}, a_i, s_i) && \text{Definition of cumulative path cost as sum of step costs} \ && &= c(s_0, a_1, s_1) + c(s_1, a_2, s_2) + \dots + c(s_{k-1}, a_k, s_k) && \text{Explicit summation over all } k \text{ transitions} \ \end{alignat*}$$

Depending on user or domain requirements, the step cost function $c(s_{i-1}, a_i, s_i)$ can prioritize different resource metrics:

• Distance-based cost: $c(s_{i-1}, a_i, s_i) = \text{miles or kilometers driven}$.
• Time-based cost: $c(s_{i-1}, a_i, s_i) = \text{travel duration accounting for traffic delays}$.
• Energy-based cost: $c(s_{i-1}, a_i, s_i) = \text{gallons of gasoline or kWh of electricity consumed}$.

2. Toy Problem Search Examples

2.1 Purpose and Value of Toy Problems in AI

2.1.1 Definition and Role of Toy Problems

In Artificial Intelligence, a toy problem is a simplified, abstract problem designed specifically for research, teaching, and algorithm testing. Rather than capturing all the messy, unpredictable details of real-world environments, toy problems strip a domain down to its core mathematical essence.

Key benefits of toy problems include:

• Safe and Controlled Environment: Allows developers to test, debug, and understand search strategies on a small scale.
• Standardized Benchmarking: Provides common, universally understood problem setups to compare algorithm performance fairly.
• Problem Formulation Practice: Offers clear practice in defining states, actions, transition models, goal tests, and path costs.
• Scalability Foundation: Builds foundational insights that directly transfer to complex real-world domains such as robotics, industrial scheduling, and route navigation.

2.2 The Vacuum World Problem

2.2.1 Environment Setup and State Space Formalization

The Vacuum World consists of a minimal $1 \times 2$ grid featuring two locations: Square A (Left) and Square B (Right).

The state representation is defined by three state variables:

1. Agent Location: The vacuum cleaner position $\text{Loc} \in {\text{Square A}, \text{Square B}}$.
2. Status of Square A: Dirt state $\text{Status}_A \in {\text{Clean}, \text{Dirty}}$.
3. Status of Square B: Dirt state $\text{Status}_B \in {\text{Clean}, \text{Dirty}}$.

The total discrete state space size $N_{\text{states}}$ is derived as:

$$\begin{alignat*}{4} && N_{\text{states}} &= |\text{Loc}| \times |\text{Status}_A| \times |\text{Status}_B| && \text{Cartesian product of independent state dimensions} \ && &= 2 \times 2 \times 2 && \text{2 location states } \times 2 \text{ dirt states for Square A } \times 2 \text{ dirt states for Square B} \ && &= 8 && \text{Total discrete states in the complete Vacuum World state space} \ \end{alignat*}$$

2.2.2 Formal 5-Tuple Formulation

The Vacuum World search problem is defined as:

• Initial State ($s_0$): Any valid configuration of agent location and dirt status (e.g., Vacuum in Square A, Square A dirty, Square B dirty).
• Actions ($Actions(s) $): $Actions(s) \in {\text{Left}, \text{Right}, \text{Suck}}$.
• Transition Model ($Result(s, a) $):
  • Action $\text{Left}$: Moves agent to Square A (no effect if already in Square A).
  • Action $\text{Right}$: Moves agent to Square B (no effect if already in Square B).
  • Action $\text{Suck}$: Changes status of the agent's current square to Clean (no effect if already clean).
• Goal Test ($IsGoal(s) $): Evaluates to True when both Square A and Square B are Clean ($\text{Status}_A = \text{Clean} \land \text{Status}_B = \text{Clean}$). The final position of the vacuum agent is irrelevant.
• Path Cost ($C(p) $): Total number of actions executed in the solution sequence (each action has a step cost of $1$).

2.2.3 Environmental Formulations and Advanced AI Concepts

The Vacuum World can be extended to demonstrate key advanced AI paradigms:

• Fully Observable Model: The agent possesses complete state information. Algorithms like $A^*$ search compute the optimal action sequence to clean all squares.
• Partially Observable Model: The agent only senses the dirt status of its current square. This hides global state features and introduces concepts of uncertainty, internal memory, reward optimization, and active sensing.
• Stochastic / Non-Deterministic Dynamics: Introduces environmental randomness where actions may fail or dirt may spontaneously reappear, serving as a testbed for stochastic search and Reinforcement Learning (RL) policies.

2.3 The Sliding Eight Tile Puzzle Problem (8-Puzzle)

2.3.1 Environment Setup and Mechanics

The Sliding Eight Tile Puzzle (8-Puzzle) consists of a $3 \times 3$ grid containing 8 numbered tiles ($1$ through $8$) and $1$ empty/blank square. A tile adjacent to the blank square can be slid into the empty space.

The problem components are formulated as follows:

• State Representation: Grid position of each numbered tile ($1$ to $8$) and the blank square.
• Initial State ($s_0$): Any valid starting tile arrangement.
• Actions ($Actions(s) $): Sliding an adjacent neighboring tile into the empty square (equivalently, moving the blank space Up, Down, Left, or Right).
• Transition Model ($Result(s, a) $): The resulting $3 \times 3$ board layout after a tile slide.
• Goal Test ($IsGoal(s) $): Checking whether the board matches the target ordered configuration (e.g., tiles in sequence $1$ through $8$ with the blank square in the designated corner).
• Path Cost ($C(p) $): Total number of moves or tile slides executed.

2.3.2 State Space Complexity and Heuristic Evaluation

While simple to describe, the state space of the 8-Puzzle is significantly large.

The mathematical derivation for the reachable state space size $N_{\text{reachable}}$ is given by:

$$\begin{alignat*}{4} && N_{\text{total}} &= 9! && \text{Total permutations of 9 distinct grid positions} \ && &= 362,880 && \text{Total mathematical board arrangements} \ && N_{\text{reachable}} &= \dfrac{N_{\text{total}}}{2} && \text{Parity constraint on sliding tile permutations} \ && &= \dfrac{362,880}{2} && \text{Applying } \dfrac{\cdot}{\cdot} \text{ fraction notation} \ && &= 181,440 && \text{Reachable state space size (> 180,000 configurations)} \ \end{alignat*}$$

2.3.3 Significance in Artificial Intelligence

The complexity of the 8-Puzzle yields key theoretical insights:

• Intractability of Brute-Force: With over 180,000 reachable states, uninformed brute-force search is inefficient, highlighting the necessity of heuristic-driven search strategies.
• Heuristic Evaluation: Serves as a standard domain to measure heuristic accuracy and evaluate effective branching factors (number of expanded nodes).
• Cross-Domain Transfer: Techniques developed for sliding tile puzzles apply directly to real-world planning, scheduling, and route navigation problems.

3. Formalizing and Setting Up a Search Problem

3.1 Search Algorithm Mechanics and Search Trees

3.1.1 Definition and Role of Search Algorithms

An algorithm is a precise, step-by-step computational procedure for solving a problem or processing input data into a desired output. In Artificial Intelligence, a search algorithm defines how an agent systematically explores available state transitions, evaluates solution progress, and selects an optimal or feasible sequence of actions from an initial state to a goal state.

Different search strategies introduce distinct operational trade-offs:

• Uninformed (blind) search strategies evaluate nodes based solely on path structure or path cost without domain-specific estimates.
• Informed (heuristic) search strategies incorporate heuristic evaluation functions to guide exploration efficiently toward the goal.

3.1.2 Search Tree Mechanics: Root Node, Node Expansion, and Successor Generation

Search algorithms explore state spaces by dynamically building a search tree:

• Root Node: Represents the initial state $s_0$ where exploration begins.
• Branches: Represent legal actions $a \in Actions(s)$ taken from a state.
• Child Nodes: Represent resulting successor states $s' = \text{Result}(s, a)$.
• Node Expansion: The process of retrieving a node $n$ from the frontier, identifying all valid actions $a \in Actions(n.\text{STATE})$, and instantiating child nodes for each generated successor state $s'$.

The critical distinction between the State Space Graph and the Search Tree is structural:

1. State Space Graph: A static representation of the problem domain $G = (V, E)$, where vertices $V$ represent unique environment states and edges $E$ represent action transitions.
2. Search Tree: A dynamic execution tree constructed during search. A single environment state $s \in V$ may correspond to multiple distinct search nodes in the search tree if reached via different action paths.

3.1.3 The General Search Loop

All classical search algorithms share a common algorithmic pipeline.

3.1.3.1 Frontier (Open List) Management

The Frontier (also termed the Open List) is the active data structure containing all generated search nodes that are pending expansion. The policy used to pop nodes from the frontier defines the specific search algorithm strategy.

3.1.3.2 Expanded / Explored Set (Closed List) Management

The Expanded Set (also termed the Closed List or Explored Set) maintains a collection of all states that have already been expanded. Storing visited states prevents duplicate expansion, eliminates redundant paths, and guarantees loop suppression in state space graphs containing cycles.

The general search algorithm loop proceeds as follows:

1. Initialize the Frontier using the root node instantiated at initial state $s_0$. Initialize the Expanded Set as empty.
2. If the Frontier is empty, terminate and return failure (no path to goal exists).
3. Remove a node $n$ from the Frontier according to the node selection strategy of the algorithm.
4. Goal Test: Check if $n.\text{STATE}$ satisfies the goal condition ($\text{IsGoal}(n.\text{STATE}) == \text{True}$). If satisfied, return the solution path by back-tracking parent pointers from $n$ to the root node.
5. Add $n.\text{STATE}$ to the Expanded Set.
6. Expand Node $n$: For each legal action $a \in Actions(n.\text{STATE})$:
   • Generate successor state $s' = \text{Result}(n.\text{STATE}, a)$.
   • Calculate step cost $c(n.\text{STATE}, a, s')$ and cumulative path cost $g(s')$.
   • Instantiate successor node $n'$.
   • If $s'$ is neither in the Frontier nor in the Expanded Set, add $n'$ to the Frontier.

3.2 Data Structures for Search Representation

3.2.1 Search Node Structure (STATE, PARENT, ACTION, PATH-COST, Priority Value)

Programmatically, a search node $n$ is a composite data structure storing five essential attributes:

1. n.STATE: The specific state space configuration $s$ represented by the node.
2. n.PARENT: A reference/pointer to the parent node that generated node $n$ (enables solution path reconstruction).
3. n.ACTION: The specific action $a$ applied to the parent node to generate $n$.
4. n.PATH-COST ($g(n) $): The total cumulative cost of the path from initial state $s_0$ to node $n$.
5. Priority Value ($f(n) $): An evaluation function value used by priority queues to order node expansion.

The cumulative path cost $g(n)$ for a node reaching state $s_k$ via sequence $(s_0, a_1, s_1, \dots, a_k, s_k)$ is derived step-by-step as:

$$ \begin{alignat*}{4} && g(s_0) &= 0 && \text{Path cost at root node} \ && g(s_k) &= g(s_{k-1}) + c(s_{k-1}, a_k, s_k) && \text{Recursive step cost accumulation} \ && &= \sum\limits_{i=1}^{k} c(s_{i-1}, a_i, s_i) && \text{Closed-form cumulative summation} \ \end{alignat*} $$

3.2.2 Environment & Grid Representation (Dimensions, Obstacle Maps, and Cell Traversal Costs)

For grid-based robotic navigation (e.g., warehouse automated guided vehicles), the environment model requires three structural representations:

1. Grid Dimensions: Defined by total rows $R$ and columns $C$, where coordinates are discrete integer tuples $(r, c)$ with $0 \le r < R$ and $0 \le c < C$.
2. Obstacle Map: A matrix $M_{obs} \in {0, 1}^{R \times C}$, where $M_{obs}[r, c] = 1$ indicates an unpassable barrier and $0$ indicates a passable cell.
3. Cell Traversal Cost Map: A matrix $W \in \mathbb{R}^{R \times C}$ where $W[r, c] > 0$ defines the movement cost associated with entering or traversing cell $(r, c)$.

During node expansion, each candidate move to coordinate $(r', c')$ undergoes explicit conditional validation:

• In-Bounds Condition: $0 \le r' < R \quad \text{and} \quad 0 \le c' < C$.
• Passability Condition: $M_{obs}[r', c'] == 0$.

Candidate moves failing either condition are discarded without instantiation into the Frontier.

3.2.3 Frontier Data Structure Implementations and Search Strategies

The operational behavior of a search algorithm depends on the concrete data structure implementing its Frontier:

3.2.3.1 FIFO Queue for Breadth-First Search (BFS)

• Data Structure: First-In, First-Out (FIFO) Queue.
• Selection Policy: Pops the oldest node in the queue (shallowest node in the search tree).
• Search Traversal: Explores the search space level-by-level.

3.2.3.2 LIFO Stack / Recursion for Depth-First Search (DFS)

• Data Structure: Last-In, First-Out (LIFO) Stack or call-stack recursion.
• Selection Policy: Pops the most recently added node (deepest node in the search tree).
• Search Traversal: Pursues a single search branch to its maximum depth before backtracking.

3.2.3.3 Priority Queue for Uniform Cost Search (UCS) and A* Search

• Data Structure: Min-Priority Queue (Min-Heap).
• Selection Policy: Pops the node with the minimum priority key $f(n)$.
• Key Specifications:
  • Uniform Cost Search (UCS): Priority key $f(n) = g(n)$ (expands nodes in order of increasing path cost).
  • A* Search: Priority key $f(n) = g(n) + h(n)$, combining actual path cost $g(n)$ with heuristic estimate $h(n)$.

4. Evaluating Search Algorithms

4.1 Classic Theoretical Evaluation Criteria

Search algorithms present fundamental trade-offs between solution quality, execution time, and memory footprint. In AI applications, evaluating an algorithm determines its suitability for specific domain requirements, such as prioritizing execution speed in real-time gaming versus guaranteeing path optimality in automated navigation.

4.1.1 Completeness: Guaranteeing Solution Discovery

Completeness evaluates whether a search algorithm is guaranteed to return a valid solution path whenever at least one solution exists in the search space.

1. Definition: An algorithm is complete if $IsGoal(s) = \text{True}$ is guaranteed to be reached in finite steps whenever a goal state exists.
2. Algorithm Dependencies:
   • Breadth-First Search (BFS): Complete in finite state spaces because it systematically expands all nodes level-by-level.
   • Depth-First Search (DFS): Incomplete in infinite search spaces or state spaces with unhandled cycles, as it can traverse endlessly down an infinite branch without backtracking.
3. Graph Search Modification: Implementing an Explored Set (Closed List) guarantees completeness for finite state spaces by preventing infinite loops caused by cyclic redundant paths.

4.1.2 Optimality: Conditions for Finding the Lowest-Cost Path

Optimality assesses whether the algorithm guarantees discovering the path $p^*$ with the minimum cumulative path cost $C(p^*)$ among all reachable goal paths.

1. Definition: Path optimality is satisfied if:

$$C(p^*) = \min\limits_{p \in P_{\text{goal}}} C(p)$$

2. Guarantees Across Search Strategies:
   • Breadth-First Search (BFS): Optimal if and only if all step costs $c(s, a, s')$ are uniform and equal to a constant $k > 0$.
   • Uniform Cost Search (UCS): Optimal for arbitrary positive step costs ($c(s, a, s') \ge \epsilon > 0$) because it expands frontier nodes strictly in increasing order of path cost $g(n)$.
   • A* Search: Optimal provided its heuristic function $h(n)$ is admissible (never overestimates true remaining cost) and consistent (monotonic).

4.1.3 Search Space Structural Parameters ($b$, $d$, $m$)

To quantify algorithmic complexity, the search tree geometry is parameterized using three fundamental structural variables:

1. Branching Factor ($b$): The average or maximum number of successor nodes generated by expanding any single state:

$$b = \dfrac{1}{|S|} \sum\limits_{s \in S} |Actions(s)|$$

2. Shallowest Goal Depth ($d$): The minimum depth level in the search tree containing a valid goal node.
3. Maximum Search Tree Depth ($m$): The maximum length or path depth of any branch in the state space tree, which may be infinite ($m = \infty$) if loops exist.

4.1.4 Asymptotic Time Complexity Analysis

Time complexity measures the computational effort of an algorithm as a function of search space dimensions, traditionally evaluated by the total number of node expansions and generated edges.

1. Uninformed Search Time Complexities:
   • BFS: $O(b^d)$ — Must generate all nodes up to depth level $d$.
   • DFS: $O(b^m)$ — May explore to the maximum tree depth $m$ before encountering a solution.
2. Informed Search Time Complexities:
   • A* Search: $O(|E| \log |V|)$ on finite graphs using a min-priority queue (where $|V|$ denotes the number of vertices/states and $|E|$ denotes the number of edges/transitions), bounded worst-case by $O(b^d)$ depending on heuristic precision.

4.1.5 Space Complexity and Memory Constraints ($O(b^d)$ vs. $O(bm) $)

Space complexity evaluates the maximum memory consumption required by the algorithm during execution, governed by the maximum number of stored nodes across the Frontier and Explored Set.

1. Memory Bounds:
   • BFS & A* Search: $O(b^d)$ — Retains all generated nodes in memory to maintain level order or path history, leading to memory exhaustion in massive search spaces.
   • DFS: $O(b \cdot m)$ — Requires linear memory space relative to maximum depth $m$, storing only nodes along the current active path and unexpanded siblings.
2. Derivation of Total Stored Nodes in BFS Tree:

$$\begin{alignat*}{4} && N_{\text{total}} &= 1 + b + b^2 + b^3 + \dots + b^d && \text{Sum of nodes across depth levels } 0 \text{ through } d \ && &= \sum\limits_{i=0}^{d} b^i && \text{Express using summation notation with limits} \ && &= \dfrac{b^{d+1} - 1}{b - 1} && \text{Sum of geometric series formula} \ && &= O(b^d) && \text{Asymptotic dominant upper bound as } b > 1 \ \end{alignat*}$$

3. Memory Optimization Strategies:
   • Iterative Deepening A* (IDA*): Combines DFS linear space efficiency $O(b \cdot m)$ with A* heuristic guidance.
   • Dynamic A* (D*): Reuses previous path search trees during local map modifications to avoid full recalculation.

4.2 Modern & Real-World Evaluation Dimensions

In industrial deployments and robotics, theoretical Big-O metrics are insufficient. Additional operational criteria determine real-world system feasibility.

4.2.1 Scalability and High-Dimensional Spaces (Sublinear Growth & RRT / PRM)

1. Definition: Scalability measures performance stability as state space size expands by orders of magnitude.
2. Sublinear Growth Requirement: Industrial algorithms require sublinear or logarithmic execution time/memory growth relative to problem size.
3. High-Dimensional Motion Planning: Classical grid search ($A^*$) fails in high-dimensional continuous configuration spaces (e.g., multi-joint robotic arms). Randomized sampling algorithms solve high-dimensional spaces:
   • Rapidly-exploring Random Trees (RRT): Randomly samples configuration space to build search trees efficiently.
   • Probabilistic Roadmaps (PRM): Constructs roadmap graphs over continuous spaces via random sampling.

4.2.2 Robustness in Dynamic Environments (Obstacle Changes & Dynamic A*)

1. Definition: Robustness measures an algorithm's ability to handle environmental uncertainty, dynamic obstacles, or unexpected state perturbation.
2. Graceful Degradation: Robust algorithms maintain sub-optimal or functional operations rather than experiencing total system failure when conditions change.
3. Dynamic Replanning (Dynamic A* / D*):
   • Classical search algorithms (BFS, A*) must discard search trees and restart from scratch when environmental obstacles change.
   • Dynamic A* (D*) updates affected path cost values incrementally by repairing existing search trees, reducing replanning latency.

4.2.3 Heuristic Quality and Effective Branching Factor ($b^* \approx N^{\dfrac{1}{d}}$)

1. Impact of Heuristic Precision: An admissible heuristic guides search toward the goal state. Heuristic accuracy dictates the total number of expanded nodes $N$.
2. Effective Branching Factor ($b^*$): The parameter $b^*$ represents the branching factor of a uniform tree of depth $d$ containing $N$ expanded nodes:

$$N + 1 = \sum\limits_{i=0}^{d} (b^*)^i = \dfrac{(b^*)^{d+1} - 1}{b^* - 1}$$

3. Approximation:

$$b^* \approx N^{\dfrac{1}{d}}$$

4. Evaluation Standard: An ideal heuristic yields $b^* \to 1$, reducing search complexity from exponential expansion down to linear progression toward the goal state.

4.2.4 Parallelizability, Learnability, and Resource / Energy Efficiency

1. Parallelizability: The capacity to distribute Frontier node expansions across multi-core CPUs, GPUs, or distributed computing clusters.
2. Learnability: The capacity of an agent to improve search heuristic quality or transition models over repeated search episodes using experience.
3. Resource & Energy Efficiency: In mobile robotics and edge computing, battery power and thermal energy consumption supersede CPU execution time as the critical limiting operational resource.