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

Re82: What is a problem? (Best-First-Search Part 1, AIMA4e pp. 73-74)

retraice.com

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.

Air date: Wednesday, 14th Dec. 2022, 11:00 PM Eastern/US.

The problem in the pseudocode

The question is: What is a problem? It seems more complicated than passing a variable or a number to a function. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC The state space (cities graph), initial state (Arad), goal state (Bucharest), and pseudocode for Best-First-Search, adapted from Russell & Norvig (2020) pp. 64, 73. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Other figures and visuals used during the livestream: * https://github.com/aimacode/aima-python/blob/master/search4e.ipynb * http://aima.cs.berkeley.edu/figures.pdf * http://aima.cs.berkeley.edu/algorithms.pdf

Formalizing a search problem:^1

We are not talking about the English-language meaning of `problem'. We're talking about a well-defined, well-formed description of something (a task environment^2). The problem is going to be an object (instance of a class, as in `object-oriented' programming) written in Python code. The following sets and functions will need to be written explicitly in Python before we can pass problem to Best-First-Search. * 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.^3

___

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.

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 Russell & Norvig (2020) pp. 42-47.

^3 Retraice (2022/12/11).