{
"cells": [
{
"cell_type": "markdown",
"id": "d9e9a31a79cf",
"metadata": {},
"source": [
"# Chapter 9: Searching the Future\n",
"\n",
"A controller can spend its planning budget exploring every continuation or use a heuristic to focus on promising routes. The heuristic buys speed by estimating remaining cost. If it exaggerates the wrong route's cost, the search can stop at a more expensive goal while a cheaper possibility waits in the queue.\n",
"\n",
"This notebook exposes both the search trace and a full-graph audit. A* uses the supplied heuristic; a separate reverse shortest-path computation establishes the true remaining costs inside this finite graph. The diagnostic can therefore distinguish helpful guidance from misleading confidence. It also accounts for heuristic evaluations, because computing a clever estimate is not free merely because the path chart omits that expense.\n",
"\n",
"**Outcome:** Execute A* and audit supplied heuristic admissibility and cost.\n",
"\n",
"- Inspect the declared input contract\n",
"- Predict the hand-checkable case\n",
"- Run the shared computation\n",
"- Change the critical assumption\n",
"- Apply the method to the transfer data\n",
"\n",
"**Guided route:** Run the worked calculation, inspect its figure, change the stated assumption, and try the transfer case. Read the explanations beside each result before opening the answers.\n",
"\n",
"**Deeper route:** First read the mathematics and canonical equation reference. Audit the input contract, predict the changed result, then inspect the shared chapter implementation and solve the questions independently. Both routes use the same calculations and preserve the equations."
]
},
{
"cell_type": "markdown",
"id": "a7781f3ee7dc",
"metadata": {},
"source": [
"## Technical Requirements\n",
"\n",
"Python 3.11 or later, the complete laboratory folder, and the notebook dependencies listed in `requirements-notebooks.txt` (the launcher's **Install notebook tools** choice installs them; see START-HERE). Standard-library chapter commands also support Python 3.10. No API key, model account or network call is used by this experiment.\n",
"\n",
"Prior knowledge:\n",
"\n",
"- Python lists and dictionaries\n",
"- The mapped chapter and its notation"
]
},
{
"cell_type": "markdown",
"id": "6bfb00c80742",
"metadata": {},
"source": [
"## The question and its mathematics\n",
"\n",
"A* orders queued states by f(n)=g(n)+h(n), where g is the best discovered path cost from the start and h estimates remaining cost. An admissible heuristic satisfies h(n)<=d*(n,goal). A consistent heuristic satisfies h(u)<=c(u,v)+h(v) for every edge and h(goal)=0.\n",
"\n",
"With nonnegative costs and an admissible heuristic, a search that reopens improved states can stop when the goal is popped and recover an optimal path. The chapter's worked graphs assume strictly positive edge costs; this finite-graph implementation also accepts zero-cost edges. That is a deliberate, valid widening: a state is queued again only when its g strictly improves, so the search terminates on a finite graph even with zero-cost cycles, and with an admissible heuristic the first popped goal is still optimal. The chapter's statements that rely on a positive-cost step are not claimed for zero-cost edges. Consistency is a stronger local condition that simplifies the behavior of expanded states. The implementation permits reopening by inserting a state again whenever its best g improves; obsolete queue entries are skipped.\n",
"\n",
"The audit computes exact remaining costs using Dijkstra's algorithm on reversed edges. This is feasible because the teaching graph is fully known. It does not mean a deployed search gets an optimal heuristic for free. Path cost, expansion count, and declared heuristic expense are separate metrics with separate units. A faster search can still consume more total compute if each heuristic call is expensive."
]
},
{
"cell_type": "markdown",
"id": "bc4ddea67504",
"metadata": {},
"source": [
"## A calculation you can run\n",
"\n",
"Register nodes and nonnegative weighted directed edges. Give every node a finite nonnegative heuristic. The function first calculates exact graph distances for diagnostic comparison, then runs A* using the supplied values. It records each expanded node's g and f, reconstructs the first popped goal path, and counts heuristic calls.\n",
"\n",
"The plot shows the g cost of successive expansions. It is a search-order trace, not a monotonic convergence curve. Consult the returned path cost and exact optimal cost together. In the changed case only B's heuristic rises. Predict which goal will be popped first and whether the admissibility check will pass. Keep the separate heuristic-total-cost metric when comparing implementations.\n",
"\n",
"The next cell finds the bundle and imports the same computation used by the chapter skill. It does not change your system Python."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "42ebefc0e5c1",
"metadata": {},
"outputs": [],
"source": [
"from pathlib import Path\n",
"import sys, json\n",
"LAB_ROOT = next((p for p in [Path.cwd(), *Path.cwd().parents] if (p / \"lab-manifest.json\").is_file()), None)\n",
"if LAB_ROOT is None:\n",
" raise RuntimeError(\"Open this notebook from the complete extracted laboratory folder.\")\n",
"sys.path.insert(0, str(LAB_ROOT / \"src\"))\n",
"from math_ai_agents.core import analyze, report_text\n",
"from math_ai_agents.plotting import figure_svg\n",
"from IPython.display import SVG, display\n"
]
},
{
"cell_type": "markdown",
"id": "7fffde8c0edb",
"metadata": {},
"source": [
"Set the declared inputs below. These are constructed teaching values, not measurements from a production agent. Change a value only after predicting what it should change."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "0413434e0274",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Chapter 9: astar-audit\n",
"Does this heuristic help search without hiding a cheaper route?\n",
"Evidence: constructed teaching example\n",
"\n",
"Calculated quantities:\n",
"{\n",
" \"path\": [\n",
" \"S\",\n",
" \"B\",\n",
" \"G\"\n",
" ],\n",
" \"path_cost\": 3.0,\n",
" \"optimal_cost\": 3.0,\n",
" \"admissible\": true,\n",
" \"consistent\": true,\n",
" \"expansions\": 3,\n",
" \"heuristic_calls\": 4,\n",
" \"heuristic_total_cost\": 0.4\n",
"}\n",
"\n",
"Interpretation:\n",
"A* stops at the first popped goal and reopens improved states. The exact reverse shortest-path check detects misleading supplied heuristics.\n",
"\n",
"Assumptions:\n",
"- Finite graph with nonnegative edge costs.\n",
"- Heuristic costs are separate from path costs.\n",
"\n",
"Limitations:\n",
"- An inadmissible heuristic can return a suboptimal goal.\n",
"- Full-graph heuristic auditing can cost more than the search itself.\n",
"\n",
"Execution: completed locally; constructed inputs are not deployment measurements.\n"
]
}
],
"source": [
"chapter = 9\n",
"inputs = {'nodes': ['S', 'A', 'B', 'G'],\n",
" 'start': 'S',\n",
" 'goal': 'G',\n",
" 'edges': [{'from': 'S', 'to': 'A', 'cost': 1},\n",
" {'from': 'A', 'to': 'G', 'cost': 4},\n",
" {'from': 'S', 'to': 'B', 'cost': 2},\n",
" {'from': 'B', 'to': 'G', 'cost': 1}],\n",
" 'heuristic': {'S': 3, 'A': 4, 'B': 1, 'G': 0},\n",
" 'heuristic_cost': 0.1}\n",
"report = analyze(chapter, inputs)\n",
"# This input was explicitly taken from the teaching fixture.\n",
"report['evidence_kind'] = 'constructed teaching example'\n",
"print(report_text(report))"
]
},
{
"cell_type": "markdown",
"id": "fd4727a26747",
"metadata": {},
"source": [
"The default shortest route is S,B,G with cost 2+1=3. The heuristic matches true remaining distances and is both admissible and consistent. A* expands toward B and reaches the cheaper goal.\n",
"\n",
"In the changed case h(B)=10 exceeds B's true remaining cost 1. The A branch looks cheaper to the queue, so the first popped goal follows S,A,G and costs 5. The exact graph optimum remains 3. The algorithm has not disproved A*; the supplied heuristic violated the condition needed for its optimality guarantee. The audit makes that violation visible beside the result.\n",
"\n",
"The plot below uses the calculated quantities. Read each panel's units before comparing its values."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "590f57e74048",
"metadata": {},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"Matplotlib is building the font cache; this may take a moment.\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(SVG(figure_svg(report)))"
]
},
{
"cell_type": "markdown",
"id": "53f372de4d2a",
"metadata": {},
"source": [
"**Figure 9.L1:** Calculated chapter experiment. Each panel labels its input and output units; interpret it under the assumptions printed in the report."
]
},
{
"cell_type": "markdown",
"id": "da76a3df42d9",
"metadata": {},
"source": [
"## Change the assumption\n",
"\n",
"An inadmissible heuristic can still return an optimal path on some graphs. That coincidence does not validate its contract. Conversely, a zero heuristic can be perfectly valid while offering no guidance beyond uniform-cost search. Evaluate correctness conditions separately from observed expansion savings.\n",
"\n",
"The full-graph diagnostic itself has a cost and requires knowledge that may not exist in an open-ended planning problem. Do not claim the audit certifies an unknown environment. Its scope is the supplied finite graph and its declared edges.\n",
"\n",
"A path can also be cheaper in edge units while more expensive in wall time, authority, or tool use. If those quantities matter, encode a justified cost model or report them separately. Adding incompatible units into one number without a valuation rule makes an apparently optimal path meaningless."
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "7b7dc6c01e3d",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Chapter 9: astar-audit\n",
"Does this heuristic help search without hiding a cheaper route?\n",
"Evidence: constructed changed-assumption example\n",
"\n",
"Calculated quantities:\n",
"{\n",
" \"path\": [\n",
" \"S\",\n",
" \"A\",\n",
" \"G\"\n",
" ],\n",
" \"path_cost\": 5.0,\n",
" \"optimal_cost\": 3.0,\n",
" \"admissible\": false,\n",
" \"consistent\": false,\n",
" \"expansions\": 3,\n",
" \"heuristic_calls\": 4,\n",
" \"heuristic_total_cost\": 0.4\n",
"}\n",
"\n",
"Interpretation:\n",
"A* stops at the first popped goal and reopens improved states. The exact reverse shortest-path check detects misleading supplied heuristics.\n",
"\n",
"Assumptions:\n",
"- Finite graph with nonnegative edge costs.\n",
"- Heuristic costs are separate from path costs.\n",
"\n",
"Limitations:\n",
"- An inadmissible heuristic can return a suboptimal goal.\n",
"- Full-graph heuristic auditing can cost more than the search itself.\n",
"\n",
"Execution: completed locally; constructed inputs are not deployment measurements.\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"changed_inputs = {'nodes': ['S', 'A', 'B', 'G'],\n",
" 'start': 'S',\n",
" 'goal': 'G',\n",
" 'edges': [{'from': 'S', 'to': 'A', 'cost': 1},\n",
" {'from': 'A', 'to': 'G', 'cost': 4},\n",
" {'from': 'S', 'to': 'B', 'cost': 2},\n",
" {'from': 'B', 'to': 'G', 'cost': 1}],\n",
" 'heuristic': {'S': 3, 'A': 4, 'B': 10, 'G': 0},\n",
" 'heuristic_cost': 0.1}\n",
"changed = analyze(chapter, changed_inputs)\n",
"changed['evidence_kind'] = 'constructed changed-assumption example'\n",
"print(report_text(changed))\n",
"display(SVG(figure_svg(changed)))"
]
},
{
"cell_type": "markdown",
"id": "02d2cef6f796",
"metadata": {},
"source": [
"**Figure 9.L2:** The changed-assumption result. Compare the printed quantities and the stated assumptions with the first run. A different input need not imply a causal effect in a deployed agent."
]
},
{
"cell_type": "markdown",
"id": "ee80b7052a50",
"metadata": {},
"source": [
"## Try a new case\n",
"\n",
"The transfer graph uses a zero heuristic. A* becomes uniform-cost search and finds source,middle,target with cost 4 instead of the direct cost 7. This is a useful baseline: correctness does not depend on a sophisticated heuristic.\n",
"\n",
"For reader data, preserve directed costs and distinguish unavailable edges from expensive edges. If you propose a heuristic, explain why it is a lower bound or label it as an unguaranteed guide. Compare its returned path with a small exact case and account for computation expense. Use graph reachability first when the main question is permission rather than cheapest continuation."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "c85b70c88fe1",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Chapter 9: astar-audit\n",
"Does this heuristic help search without hiding a cheaper route?\n",
"Evidence: constructed transfer example\n",
"\n",
"Calculated quantities:\n",
"{\n",
" \"path\": [\n",
" \"source\",\n",
" \"middle\",\n",
" \"target\"\n",
" ],\n",
" \"path_cost\": 4.0,\n",
" \"optimal_cost\": 4.0,\n",
" \"admissible\": true,\n",
" \"consistent\": true,\n",
" \"expansions\": 3,\n",
" \"heuristic_calls\": 4,\n",
" \"heuristic_total_cost\": 0.0\n",
"}\n",
"\n",
"Interpretation:\n",
"A* stops at the first popped goal and reopens improved states. The exact reverse shortest-path check detects misleading supplied heuristics.\n",
"\n",
"Assumptions:\n",
"- Finite graph with nonnegative edge costs.\n",
"- Heuristic costs are separate from path costs.\n",
"\n",
"Limitations:\n",
"- An inadmissible heuristic can return a suboptimal goal.\n",
"- Full-graph heuristic auditing can cost more than the search itself.\n",
"\n",
"Execution: completed locally; constructed inputs are not deployment measurements.\n"
]
}
],
"source": [
"transfer_inputs = {'nodes': ['source', 'middle', 'target'],\n",
" 'start': 'source',\n",
" 'goal': 'target',\n",
" 'edges': [{'from': 'source', 'to': 'middle', 'cost': 2},\n",
" {'from': 'middle', 'to': 'target', 'cost': 2},\n",
" {'from': 'source', 'to': 'target', 'cost': 7}],\n",
" 'heuristic': {'source': 0, 'middle': 0, 'target': 0},\n",
" 'heuristic_cost': 0}\n",
"transfer = analyze(chapter, transfer_inputs)\n",
"transfer['evidence_kind'] = 'constructed transfer example'\n",
"print(report_text(transfer))"
]
},
{
"cell_type": "markdown",
"id": "9cb4861bf499",
"metadata": {},
"source": [
"## Apply the method to your inputs\n",
"\n",
"The example file below has the exact input shape the method accepts. Copy it to a new file, replace its values, then point `reader_file` at your copy. Run the cell again. Supplied inputs retain their stated provenance; the program cannot establish that they are representative observations.\n",
"\n",
"- **nodes:** Unique graph identifiers.\n",
"- **start:** Registered search start.\n",
"- **goal:** Registered goal.\n",
"- **edges:** Directed from/to identifiers with finite nonnegative cost.\n",
"- **heuristic:** Object mapping each node to a nonnegative estimated remaining cost.\n",
"- **heuristic_cost:** Nonnegative declared cost of one heuristic evaluation, separate from path cost."
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "80cf6ecf2c36",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Chapter 9: astar-audit\n",
"Does this heuristic help search without hiding a cheaper route?\n",
"Evidence: supplied local inputs; provenance not independently verified\n",
"\n",
"Calculated quantities:\n",
"{\n",
" \"path\": [\n",
" \"source\",\n",
" \"middle\",\n",
" \"target\"\n",
" ],\n",
" \"path_cost\": 4.0,\n",
" \"optimal_cost\": 4.0,\n",
" \"admissible\": true,\n",
" \"consistent\": true,\n",
" \"expansions\": 3,\n",
" \"heuristic_calls\": 4,\n",
" \"heuristic_total_cost\": 0.0\n",
"}\n",
"\n",
"Interpretation:\n",
"A* stops at the first popped goal and reopens improved states. The exact reverse shortest-path check detects misleading supplied heuristics.\n",
"\n",
"Assumptions:\n",
"- Finite graph with nonnegative edge costs.\n",
"- Heuristic costs are separate from path costs.\n",
"\n",
"Limitations:\n",
"- An inadmissible heuristic can return a suboptimal goal.\n",
"- Full-graph heuristic auditing can cost more than the search itself.\n",
"\n",
"Execution: completed locally; constructed inputs are not deployment measurements.\n"
]
}
],
"source": [
"reader_file = LAB_ROOT / 'data/examples/ch09.json'\n",
"reader_inputs = json.loads(reader_file.read_text())\n",
"reader_report = analyze(chapter, reader_inputs)\n",
"print(report_text(reader_report))"
]
},
{
"cell_type": "markdown",
"id": "b7444ffabe30",
"metadata": {},
"source": [
"## Questions\n",
"\n",
"1. What is the default optimal path cost?\n",
"\n",
"2. Which changed heuristic condition fails?\n",
"\n",
"3. What does h=0 produce?\n",
"\n",
"Answers: [separate solutions](../solutions/ch09.md). Try the calculation before opening them."
]
},
{
"cell_type": "markdown",
"id": "6de6057b7f9c",
"metadata": {},
"source": [
"## Summary\n",
"\n",
"A* combines accumulated cost with a remaining-cost estimate. Its trace is useful only when interpreted with heuristic conditions and computation expense. The default reaches the optimum; the changed heuristic hides the cheaper branch; the transfer case establishes a zero-heuristic baseline. The audit applies to a fully supplied finite graph. It checks a mathematical condition without estimating real-world edge accuracy or granting permission to traverse a route.\n",
"\n",
"Limits of this experiment:\n",
"\n",
"- This is a local calculation under declared inputs, not an empirical claim about a deployed agent.\n",
"- Read the returned assumptions and limitations before applying the numerical result.\n",
"\n",
"The assistant skill is [`maa-09-astar-audit`](../skills/maa-09-astar-audit/SKILL.md). It uses this notebook's tested computation and input contract."
]
},
{
"cell_type": "markdown",
"id": "9cc9f25ba898",
"metadata": {},
"source": [
"## Equations from the chapter\n",
"\n",
"These are the unchanged display equations and their explanations from the canonical chapter. They are a reference for the experiment, not a claim that every equation is numerically implemented by this one method."
]
},
{
"cell_type": "markdown",
"id": "363bab05f674",
"metadata": {},
"source": [
"### Equation 9.1\n",
"\n",
"\n",
"\n",
"Equation (9.1) gives the cost of the best route that is forced to pass through a particular vertex.\n",
"\n",
"Add the cheapest way of getting to the vertex to the cheapest way of finishing from it.\n",
"\n",
"LaTeX source, preserved for inspection:\n",
"\n",
"```latex\n",
"f(v) \\;=\\; g(v) \\;+\\; h(v).\n",
"\\tag{9.1}\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "6fd3f9547654",
"metadata": {},
"source": [
"### Equation 9.2\n",
"\n",
"\n",
"\n",
"Equation (9.2) is the computable stand-in for Equation (9.1), and it is what the search actually sorts on.\n",
"\n",
"Add what the search has already spent reaching the vertex to what it guesses finishing will cost.\n",
"\n",
"LaTeX source, preserved for inspection:\n",
"\n",
"```latex\n",
"\\hat f(v) \\;=\\; \\hat g(v) \\;+\\; \\hat h(v).\n",
"\\tag{9.2}\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "1acde2150089",
"metadata": {},
"source": [
"### Equation 9.3\n",
"\n",
"\n",
"\n",
"Equation (9.3) is the condition under which the search cannot be talked out of the best path.\n",
"\n",
"Never guess that finishing will cost more than it actually will.\n",
"\n",
"LaTeX source, preserved for inspection:\n",
"\n",
"```latex\n",
"\\hat h(v) \\;\\le\\; h(v) \\qquad \\text{for every vertex } v.\n",
"\\tag{9.3}\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "9643cc217d86",
"metadata": {},
"source": [
"### Equation 9.4\n",
"\n",
"\n",
"\n",
"Equation (9.4) requires the estimate to be consistent with itself from one vertex to the next.\n",
"\n",
"The true cost of getting from one vertex to another, plus the estimate at the second, must be at least the estimate at the first.\n",
"\n",
"LaTeX source, preserved for inspection:\n",
"\n",
"```latex\n",
"h(u,v) \\;+\\; \\hat h(v) \\;\\ge\\; \\hat h(u).\n",
"\\tag{9.4}\n",
"```"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Mathematics of AI Agents",
"language": "python",
"name": "maa-lab"
},
"lab_chapter": 9,
"lab_execution": {
"code_cells": 6,
"created_utc": "2026-10-02T05:14:15.145212+00:00",
"elapsed_seconds": 8.766718999948353,
"method": "fresh process; new ipykernel InProcessKernelManager; cells submitted as Jupyter execute requests",
"network_transport_tested": false,
"python": "3.11.15",
"source_sha256": "d1931e3495e3914a86732e70389ecd1b719b219f633b705d2e2867cd67a2907f"
},
"language_info": {
"name": "python"
}
},
"nbformat": 4,
"nbformat_minor": 5
}