Problem Representation in AI PDF

IT2206 Problem Representation in AI 3. Selection – This step covers the sele...

IT2206 Problem Representation in AI 3. Selection – This step covers the selection of the best technique Problem Representation and/or methodologies for solving a specific problem. Simulation of In artificial intelligence (AI), a problem can be formally defined through the multiple sequences of actions may be performed in this step, that may following attributes (Russell & Norvig, 2022): either reach the goal or not. A state space which is a set of possible states that the environment can 4. Execution – This step involves the execution of a completed solution be in: This can be represented as a graph in which the vertices are states by the agent. and the directed edges between them are actions. The initial state that the agent starts in Every problem formulation involves abstractions. Abstraction is the process A set of one or more goal states of removing details from a representation. A good problem formulation has the The actions available to the agent: A sequence of actions forms a path, right level of abstraction. A good abstraction involves removing as much details and a solution is a path from the initial state to a goal state. as possible while retaining validity and ensuring that the abstracted actions are A transition model that describes what each action does still easy to execute (Russell & Norvig, 2022). An action cost function reflects a problem-solving agent's own o Abstraction is valid if elaborating the details of any abstracted solution performance measure is still possible. o Abstraction is beneficial if carrying out actions in a solution becomes A standardized problem is intended to illustrate or exercise various problem- easier. solving methods. It can be given a concise. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare Problem Characterization the performance of algorithms. A real-world problem, on the other hand, To choose the most appropriate method for a particular problem in AI, it is encompasses formulations that are idiosyncratic and not standardized, while necessary to check the problem in light of the following considerations (Gupta the solutions are utilized by the general population. & Mangla, 2020): A large and composite problem can be easily solved if it can be broken Problem-solving agents are agents that consider a sequence of actions that down into smaller problems and recursion can be applied. Thus, the form a path to a specific goal. These agents utilize atomic representations that question would be: Can the problem be broken down into a smaller or have no internal structure visible to the problem-solving algorithms. On the easier sub-problem? other hand, agents that utilize structured representations of different states are AI problems can be classified based on the steps of the solutions to a called planning agents. Note that one important property in problem problem. These classifications are: representation is that in a fully observable, deterministic, known environment, o Ignorable such as theorem proving; the solution to any problem is a fixed sequence of actions (Russell & Norvig, o Recoverable such as the 8-puzzle game, wherein the solution 2022). steps can be undone; and o Irrecoverable such as checkers, wherein the solution steps The following are the general steps required in building systems that solve AI- cannot be undone. related problems (Gupta & Mangla, 2020; Russell & Norvig, 2022): An AI program must implement an internally consistent knowledge base. 1. Problem Definition – This step involves the precise specifications of The fundamental criterion for a system to be classified as an AI program what the initial situation will be, as well as the possible final situations is that it must require and use a great amount of knowledge to formulate that constitute acceptable solutions to a specified problem. viable solutions. 2. Problem Analysis – This step has an immense impact on the AI programs require periodic interactions between humans and computers appropriateness of various possible techniques and/or methodologies since these programs assist humans in making the right decisions. for solving a specified problem. AI programs must have the capability to handle uncertainty and incomplete and irrelevant information. 02 Handout 1 *Property of STI  [email protected] Page 1 of 4  IT2206 AI programs also encompass heuristic (experiential) search, which o The initial state can be represented as: involves a variety of techniques to solve a large class of problems. Note (4, 5, 0), (8, 1, 6), (3, 7, 2) that heuristics are also used for problems where no general algorithms are o The goal state can be represented as: known. (0, 1, 2), (3, 4, 5), (6, 7, 8) An essential characteristic of an AI program is its ability to learn, without o The actions can be set in terms of direction: which the modern systems could not have achieved the advanced Up, down, left, and right technological level they are at today. 2. The Water Jug Problem: Imagine a 3-liter jug (small jug), a 5-liter jug Methods of Problem Representation (large jug), and an unlimited supply of water. The goal is to get exactly State Space Representation one (1) liter of water into either jug. Either jug can be emptied/filled or This method defines problems in the form of states. The term state specifically poured into the other. pertains to a position at a certain time. It is a straightforward approach for planning an algorithm since it implements the state space search that A state in this problem could be represented with a pair of numbers. considers everything that is needed for finding a solution. There are two (2) The first number represents the volume of water in the small jug, while possible ways to implement a state space search: the second number represents the volume of water in the large jug. Forward state space search – The process begins at the problem's initial state and considers sequences of actions until the specified goal state is reached. It is sometimes referred to as progression planning since it moves in a forward direction (Gupta & Mangla, 2020). Backward state space search – This type of state space search can be difficult to implement since the goal states are described by a set of constraints that are not listed explicitly. Nonetheless, one of its main Figure 2. A sample illustration of the water jug problem. advantages is that it allows the consideration of relevant actions only (Subarna, n.d.). It is sometimes referred to as regression planning since it o The initial state would be (0, 0), which represents both jugs are finds the solution from the goal to the starting stage. empty at the beginning. o The sequence of actions regarding this problem may include the Examples of state space representation (Gupta & Mangla, 2020): following procedures: a. Fill the 3-liter jug to its maximum capacity from the water source. 1. The 8-puzzle: This involves a 3x3 grid (game board) with eight (8) b. Fill the 5-liter jug to its maximum capacity from the water source. consecutively numbered tiles arranged on it. Any tile adjacent to the c. Empty the large jug into a drain. space (the tile labeled with zero) can be moved and several different d. Pour the water from the small jug into the large jug. So, there is goal states may be used. A state problem needs to keep track of the still space for 2 liters of water in the large jug. position of all the tiles on the grid. e. Fill the small jug to its maximum capacity. f. Pour 2 liters of water from the small jug into the large jug. Now, the large jug is full and there is 1 liter of water remaining in the small jug. g. Empty the large jug into a drain. h. The goal state is reached. Note: The actions and/or procedure may vary depending on the problem solving approach. o The goal state would be represented as (1, 0). Figure 1. A sample illustration of an 8-puzzle. 02 Handout 1 *Property of STI  [email protected] Page 2 of 4  IT2206 Deficiencies of the state space representation (Gupta & Mangla, 2020): Production Systems Displaying all possible states for a given problem is not possible. A production system provides the necessary mechanism that describes and This method explores massive models rather than applying a factored executes the search process which primarily contains a set of rules about perspective. behavior, commonly called production rules. Productions rules are basic The computer system resources are limited in handling massive state representations that are useful in automated planning, expert systems, and space representation. action selection. The following are the components of a production system It is time-consuming to process. (Gupta & Mangla, 2020): Programs that implement this method do not learn from mistakes and Set of Production Rules: A production system is generally composed of hence, tend to commit the same mistake repeatedly. two (2) parts, a sensory precondition (the "IF" statement) and the action (the "THEN" statement). If the production system's precondition matches Problem Reduction the current state, then the production system is said to be triggered. If the The problem reduction search is a basic problem-solving technique in production system's action is executed, then it is said to have fired. artificial intelligence that involves the reduction of a complex problem to a set Working Memory – A Global Database: The working memory is the of less complicated sub-problems whose solutions, if found, can be combined central data structure used by an artificial intelligence production system. to form the solution to the actual problem. This can be easily written as a The production rules operate using a global database. Each rule recursive program. Problem reduction can be graphically represented with the encompasses a precondition that is either satisfied or not by the database. aid of AND and OR graphs or the AND-OR tree (Gupta & Mangla, 2020). If the precondition is satisfied, then the production rule can be applied. o The AND relationship solutions for a problem can be obtained by Note that the application of production rules changes the database. solving all the sub-problems, corresponding to the AND gate condition Control System: This chooses appropriate production rules that must be that it will only be true if and only if all the inputs are true. applied and ceases computation when termination conditions for the o The OR relationship solutions for a problem can be obtained by database are satisfied. The control system also resolves conflict whenever solving any of the sub-problems. several procedures are to fire at the same time. Rule Applier: This is considered as the core unit of a production system, since production rules are applied with the aid of the rule applier. Conflict Resolution Schemes: These are simple strategies used in a production system that help in choosing which production rule to fire. These are dependent on the number of conditions in the production or the time stamp of the elements to which the conditions matched, or they may be completely random. Conflict resolution schemes can be categorized as follows: o Specificity – If all conditions of two (2) or more production rules are satisfied, choose the rule with the most specific condition. This is also referred to as the degree of specialization. o Recency – When two (2) or more production rules could be chosen, the system favors the one that matches the most current since it is generally believed that a newly added rule contains more information than the existing ones. o Refraction – Once a rule has fired, it may not fire again until the Figure 3. Problem reduction using the AND-OR tree. working memory elements that match its conditions have been modified. It generally helps a system avoid entering infinite loops. 02 Handout 1 *Property of STI  [email protected] Page 3 of 4  IT2206 o Order – This picks the first applicable production rule based on Space complexity: How much memory is needed to perform the the order of presentation. It is one of the most common conflict algorithm? resolution strategies. A complete algorithm must be capable of systematically exploring every Advantages of Production Systems (Gupta & Mangla, 2020): reachable state, starting from the initial state. Problem-solving algorithms must Individual production rules can be added, modified, or removed also be systematic in the way it explores an infinite state space. The time and independently in a production system. Hence, production systems are space complexity are then measured with respect to the difficulty of the highly modular. problem. In artificial intelligence, production systems provide an excellent tool for structuring. In many AI problems, graphs are represented implicitly through the initial state, The production rules are expressed in a natural form. Thus, the statements actions, and transition model. For an implicit state space, complexity can be in a knowledge base should be similar to a recording of an expert thinking measured in terms of the following (Russell & Norvig, 2022): aloud. d – depth; the number of actions in an optimal solution The syntactic independence of production system models supports the m – the maximum number of actions in any path incremental development of expert systems by successively adding, b – branching factor; the number of subsequent nodes that need to be changing, or deleting the knowledge (production rules) of the system. considered. The knowledge and control system are separated. This makes knowledge References: base modification easier and sudden changes in the code for program Gupta, N. & Mangla, R. (2020). Artificial intelligence basics: A self-teaching introduction. Mercury Learning and Information LLC control are not required. Russell, S. & Norvig, P. (2022). Artificial Intelligence: A modern approach (4th ed.). Pearson Education Limited Subarna D. (n.d.). Planning methods: State-space search & goal stack | Artificial intelligence. Retrieved on February 3, 2022 from The computational complexity is deterministically finite, and the conflict https://www.engineeringenotes.com/artificial-intelligence-2/planning-methods-state-space-search-goal-stack-artificial- resolution scheme is trivial. intelligence/35248 Disadvantages of Production Systems (Gupta & Mangla, 2020): Production rules are inadequate in expressing and describing situations. As the number of production rules increases, the difficulty of checking for redundancy and rule conflict also increases. The control flow analysis within the production system is difficult since individual rules do not call each other. Measuring Problem-solving Performance The performance of algorithms involved in artificial intelligence (AI) problem- solving can be evaluated through the following criteria (Russell & Norvig, 2022): Completeness: Can the algorithm guarantee to find a solution (when there is one) and correctly report failure (when there is no possible solution)? Cost optimality: Can the algorithm find a solution with the lowest path cost among all workable solutions? Time complexity: How long does it take to find an optimal solution? 02 Handout 1 *Property of STI  [email protected] Page 4 of 4