(The below text version of the notes is for search purposes and convenience. See the PDF version for proper formatting such as bold, italics, etc., and graphics where applicable. Copyright: 2022 Retraice, Inc.)
Re97: Recap of BFS
(Best-First-Search Part 15, AIMA4e pp. 73-74)
retraice.com
A summary of how the AIMA-Python implementation of BFS works and what it took to learn it.
Final version of verbose BFS in Re95 Notes; starting from AIMA4e p. 73 and the task of passing a problem and an evaluation function to an agent program; discovering the nature of formalizing a problem, state space, evaluation function, node and frontier; the ins and outs of making even a simple agent program work; learning Python and object-oriented programming along the way; getting from A to B. Highlights from the livestream: overview; Re82 formal problems, Re84 nodes, Re90 problem implementation, Re95 final execution; the len call, and straight-line distances vs. road distances; the program running, and source.
Air date: Tuesday, 27th Dec. 2022, 10:00 PM Eastern/US.
Re82: What is a problem? (Best-First-Search Part 1, AIMA4e pp. 73-74)^1
Using sets and functions to formalize problems.
Passing a problem to a function vs. passing a variable or number; English meaning and formal meaning of problem; problem as description of task environment; problem as object instantiating class, written in Python; state space, initial state, goal state(s), actions, transition model, action cost function, evaluation function.
Re83: A Problem Instantiated (Best-First-Search Part 2, AIMA4e pp. 73-74)^2
Writing a well-defined problem, in Python, as an object that's an instance of the class Problem.
Object-oriented programming; class Problem as subclass of object, implementing structure of well-defined problem; initial state and goal state as attributes in Problem; the four functions Actions(), Result(), Is-Goal() and Action-Cost(), and the informed search function h(), as methods in Problem.
Re84: A Node Instantiated (Best-First-Search Part 3, AIMA4e pp. 73-74)^3
Writing, as a class in Python, a data structure to represent a reached state in the environment's state space.
State space and search tree; nodes and edges; nodes as representing unique paths; parent nodes, applied actions and total path-from-initial-state cost; init, repr, len and lt magic methods in Python.
Re85: The Details (Best-First-Search Part 4, AIMA4e pp. 73-74)^4
Looking ahead at the code we'll need.
An attempt to build a toy problem reveals unsatisfied dependencies; the need for a problem implementation with state space, actions sets, transition model and action cost function; AIMA's RouteProblem class and best_first_search function implementations as guides; walking through the suites of each; the need for PriorityQueue and f to order our search tree's frontier of nodes.
Re86: Code Reading (Best-First-Search Part 5, AIMA4e pp. 73-74)^5
Getting used to the components of a search problem and algorithm implemented in Python.
The Problem class and its place-holder methods; the RouteProblem subclass and its more substantial methods; the Map class, and neighbors as actions; the links argument to Map as actions, the locations argument as states; the multimap function as the key to generating a list of neighbors (actions).
Re87: The multimap Function, Part A (Best-First-Search Part 6, AIMA4e pp. 73-74)^6
Unpacking the code that gets us the neighbors of our current state which are the actions available in the Romania problem.
The connections between Map and multimap; hasattr; 'items'; adding reverse actions to our state space; neighbors, actions and multimap; probing objects with dir() and __dict__; causing side effects by calling a function from inside a class; debugging.
Re88: The multimap Function, Part B (Best-First-Search Part 7, AIMA4e pp. 73-74)^7
Finishing what we started with multimap.
Using verbose printing to watch the behavior of multimap; demonstrating the side-effects behavior of executing Map, which calls multimap and passes a modified tlinks to it; but it's not clear why the Map-modified tlinks would be the same object as the global tlinks.
Re89: The multimap Function, Part C (Best-First-Search Part 8, AIMA4e pp. 73-74)^8
How multimap works.
Code and math vs. AI; Retraice code quality issues; Map passes a modified links to multimap; multimap creates a defaultdict, a dict with default values, from collections; multimap then strips the values from the links dictionary, and parses the keys, which should be pairs, into key-value pairs for the new dictionary of neighbors,
i.e. actions available at each state.
Re90: The Map Class (Best-First-Search Part 9, AIMA4e pp. 73-74)^9
How instantiations of Map work.
The attributes of Map are locations, neighbors and distances; multimap produces the neighbors dictionary; tlinks has the actions (in pairs of states) and cost values in miles of our state space tmap; tlocations has the states of tmap; Problem has our initial and goal states as attributes, and the is_goal method; RouteProblem has our actions, result and action_cost methods.
Re91: The PriorityQueue Class, Part A (Best-First-Search Part 10, AIMA4e pp. 73-74)^10
Trying to make PriorityQueue work by fiddling with evaluation functions.
Given the AIMA Python source code, we can now provide a test map with actions and locations (i.e. a state space), a test problem with initial state, goal state and state space, a test evaluation function to order our queue of nodes, and run best_first_search without throwing an error; the output, though, does not seem like a solution.
Re92: The PriorityQueue Class, Part B (Best-First-Search Part 11, AIMA4e pp. 73-74)^11
From best_first_search to Node to PriorityQueue to frontier.
Trying to understand the insides of PriorityQueue; executing lines manually, outside of the class; the first node as initial state; the items of the frontier instantiation of PriorityQueue.
Re93: The PriorityQueue Class, Part C (Best-First-Search Part 12, AIMA4e pp. 73-74)^12
Examining Nodes and their handling by PriorityQueue.
The first node in BFS is our problem initial state, and is returned as specified by the Node class repr method; nodes passed to PriorityQueue must be iterable so plain nodes and tuple nodes don't work, but dictionary nodes and string nodes do.
Re94: The PriorityQueue Class, Part D (Best-First-Search Part 13, AIMA4e pp. 73-74)^13
Making BFS and PriorityQueue chatty to increase our confidence in their output.
Printing messages throughout the execution of best_first_search and PriorityQueue; the states of node, frontier and reached as they change during execution; the attributes of a solution node.
Re95: The PriorityQueue Class, Part E (Best-First-Search Part 14, AIMA4e pp. 73-74)^14
frontier is a PriorityQueue which is built on heapq and uses f to create (score, item) pairs to be queued.
Printing verbose updates as BFS proceeds, using PriorityQueue, from A to B, including calculating straight-line distances as a heuristic (f1); the frontier list (PriorityQueue) and reached dictionary can be seen growing; the selection of nodes from children is based on the ordering of the frontier PriorityQueue using f1, the evaluation function.
_
References
Retraice (2022/12/14). Re82: What is a problem? (BEST-FIRST-SEARCH Part 1, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re82Retrieved 15th Dec. 2022.
Retraice (2022/12/15). Re83: A Problem Instantiated (BEST-FIRST-SEARCH Part 2, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re83Retrieved 16th Dec. 2022.
Retraice (2022/12/16). Re84: A Node Instantiated (BEST-FIRST-SEARCH Part 3, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re84Retrieved 17th Dec. 2022.
Retraice (2022/12/17). Re85: The Details (BEST-FIRST-SEARCH Part 4, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re85Retrieved 18th Dec. 2022.
Retraice (2022/12/18). Re86: Code Reading (BEST-FIRST-SEARCH Part 5, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re86Retrieved 19th Dec. 2022.
Retraice (2022/12/19). Re87: The multimap Function, Part A (BEST-FIRST-SEARCH Part 6, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re87Retrieved 20th Dec. 2022.
Retraice (2022/12/20). Re88: The multimap Function, Part B (BEST-FIRST-SEARCH Part 7, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re88Retrieved 21st Dec. 2022.
Retraice (2022/12/21). Re89: The multimap Function, Part C (BEST-FIRST-SEARCH Part 8, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re89Retrieved 22nd Dec. 2022.
Retraice (2022/12/22a). Re90: The Map Class (BEST-FIRST-SEARCH Part 9, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re90Retrieved 23rd Dec. 2022.
Retraice (2022/12/22b). Re91: The PriorityQueue Class, Part A (BEST-FIRST-SEARCH Part 10, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re91Retrieved 24th Dec. 2022.
Retraice (2022/12/23). Re92: The PriorityQueue Class, Part B (BEST-FIRST-SEARCH Part 11, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re92Retrieved 24th Dec. 2022.
Retraice (2022/12/24). Re93: The PriorityQueue Class, Part C (BEST-FIRST-SEARCH Part 12, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re93Retrieved 25th Dec. 2022.
Retraice (2022/12/25). Re94: The PriorityQueue Class, Part D (BEST-FIRST-SEARCH Part 13, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re94Retrieved 26th Dec. 2022.
Retraice (2022/12/26a). Re95: The PriorityQueue Class, Part E (BEST-FIRST-SEARCH Part 14, AIMA4e pp. 73-74). retraice.com.
https://www.retraice.com/segments/re95Retrieved 27th Dec. 2022.
Retraice (2022/12/26b). Re96: News of ChatGPT, Part 1. retraice.com.
https://www.retraice.com/segments/re96Retrieved 27th Dec. 2022.
Footnotes
^1 Retraice (2022/12/14). ^2 Retraice (2022/12/15). ^3 Retraice (2022/12/16). ^4 Retraice (2022/12/17). ^5 Retraice (2022/12/18). ^6 Retraice (2022/12/19). ^7 Retraice (2022/12/20). ^8 Retraice (2022/12/21). ^9 Retraice (2022/12/22a). ^10 Retraice (2022/12/22b). ^11 Retraice (2022/12/23). ^12 Retraice (2022/12/24). ^13 Retraice (2022/12/25). ^14 Retraice (2022/12/26a).
