UNIT:II

Dr S Naganjaneyulu

Syllabus

• Searching: Searching for solutions, uniformed search strategies – Breadth first search, depth first Search. Search with partial information (Heuristic search) Hill climbing, A* ,AO* Algorithms, Problem reduction, Game Playing-Adversial search, Games, minmax algorithm, optimal decisions in multiplayer games, Problem in Game playing, Alpha Beta pruning, Evaluation functions..

​

​

Chapter-3 Textbook1

Problem-Solving Agents

• Intelligent agents are supposed to maximize their performance measure. Achieving this is possible if the agent can adopt a goal and aim at satisfying it.
• Ex: agent has a non refundable ticket to fly out of India the following day.
• It make sense for the agent to adopt the goal of getting to India.
• Courses of action that don’t reach India on time can be rejected without any considerations and agents decision problem is greatly simplified.
• Goals help organize the behaviour by limiting the objectives that the agent is trying to achieve.

• Goal Formulation: This one is the first and simple step in problem-solving. It organizes finite steps to formulate a target/goals which require some action to achieve the goal.
• Ex: moving from car parking.
• Problem formulation: It is one of the core steps of problem-solving which decides what actions and states should be consider to achieve the formulated goal.
• Search:
• Search is fundamental to the problem-solving process.
• Search is a general mechanism that can be used when more direct method is not known.
• Search provides the framework into which more direct methods for solving subparts of a problem can be embedded.

A very large number of AI problems are formulated as search problems

​

​

​

• The process of looking for a sequence of actions is called search.
• A search algorithm takes a problem as input and returns a solution in the form of an action sequence.
• Once a solution is found, the action it recommends can be carried out. This is called the execution phase.

​

Well defined problems and solutions

A Problem can be defined formally by four components: 

1. Initial State:  which starts the AI agent towards a specified goal.

2. Action: This stage of problem formulation works with function with a specific class taken from the initial state and all possible actions done in this stage.

• Successor function: A Successor Function is needed for state change. The successor function moves one state to another state.
• Successor Function :
• Is a description of possible actions; a set of operators.
• Is a transformation function on a state representation, which converts that state into another state.
• Defines a relation of accessibility among states.
• Represents the conditions of applicability of a state and corresponding transformation function

3. Goal test: This stage determines that the specified goal achieved by the integrated transition model or not, whenever the goal achieves stop the action and forward into the next stage to determine the cost to achieve the goal.  

4. Path cost: This component assigns a numeric cost to each path.

​

Example:

Formulation of Problems Examples:

Searching for Solutions

Depth First Search

Breadth First Search

• h(n) is a heuristic function that estimates cost of the cheapest path from node ‘n’ to the goal node