Notes by Retraice - SoundSage

(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.)

Re86: Code Reading (Best-First-Search Part 5, AIMA4e pp. 73-74)

retraice.com

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).

Air date: Sunday, 18th Dec. 2022, 10:00 PM Eastern/US.

Problem and RouteProblem

Most of the code below is from https://github.com/aimacode/aima-python/blob/master/search4e.ipynb. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Formalizing a search problem (from Re82):^1

state space: a set of possible states of the environment; * initial state: the state in which the agent starts; * goal state(s): a set of one or more; account for one, some, infinite (by means of a property) by specifying Is-Goal method for problem; * actions: what the agent can do; Actions(state) returns a finite set of actions that can be executed in state; * transition model: describes what actions do; Result(state,action) returns the state s' that results from doing action in state; * action cost function: Action-Cost(s,a,s') gives the numeric cost of applying action a in state s to reach new state s'. Cf. the evaluation function, which we'll use to prioritize our nodes for next expansion, and the objective function, which was our cost measure to be minimized in the airport problem.^2

Map, multimap and romania ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

best_first_search ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Other sources consulted during this livestream: * Russell & Norvig (2020); * Retraice (2022/12/14); * Retraice (2022/12/15); * Retraice (2022/12/16); * Retraice (2022/12/17); * http://aima.cs.berkeley.edu/figures.pdf; * https://github.com/aimacode/aima-python/blob/master/search4e.ipynb; * https://github.com/retraice/ReAIMA4e/tree/main/Re85-BEST-FIRST-Part-4.

References

Retraice (2022/12/11). Re78: Recap of Gradients and Partial Derivatives (AIMA4e pp. 119-122). retraice.com. https://www.retraice.com/segments/re78 Retrieved 12th Dec. 2022.

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/re82 Retrieved 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/re83 Retrieved 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/re84 Retrieved 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/re85 Retrieved 18th Dec. 2022.

Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. Pearson, 4th ed. ISBN: 978-0134610993. Searches: https://www.amazon.com/s?k=978-0134610993 https://www.google.com/search?q=isbn+978-0134610993 https://lccn.loc.gov/2019047498

Footnotes

^1 Russell & Norvig (2020) p. 65.

^2 Retraice (2022/12/11).

See All 145 Episodes of "Notes by Retraice"