Search strategies

•A search strategy is defined by picking the order of node expansion

•Strategies are evaluated along the following dimensions:

–completeness: does it always find a solution if one exists?

–time complexity: number of nodes generated

–space complexity: maximum number of nodes in memory

–optimality: does it always find a least-cost solution?

General tree search

Real world problem

Real world problem :

•Touring problem.

•Traveling sales man problem.

•VLSI. (component connections on chip, minimize-area, circuit delay, capacitance, maximize-manufacturing yield)

•Automatic assemble problem. (assemble the parts of some objects, protein design-to find sequence of amino acid)

•Internet searching. (looking for answer to questions)

 

Four components of a Well-defined problems

Four components

•Initial state.

•Successor function.

•Goal test.

•Path cost.

 

Initial state:

   The agent starts in.

Successor function:

   Given a state x,SUCCESSOR-FN(x)Returns a set of < action,successor> ordered pairs.

•The initial state and successor function define the state space.

 Goal test :

   Whether the given state is a goal state?

Path cost:

  Assigns numeric cost to each path.Step cost for taking action a from state x to y-denoted by c(x,a,y).

Solution:

  A path from initial to a goal state.

Solution quality:

   measured by cost.

Optimal solution:

   Lowest path cost among all solutions.

Save water:

Espure Water Solution Pvt Ltd 

Chennai,India.

www.espure.in

Mobile: 9944116631 / 9841005335

Effluent Treatment Plant Manufacturer in Chennai

http://enpure.in/effluent-treatment-plant/

Problem solving agent

•Goal formulation:

   Based on current situation and the agent’s performance measure-first step in problem solving.

•Problem formulation:

   Deciding what actions and state to consider, given a goal.

•An agent with several immediate options of unknown value can decide what to do by first examining different possible sequences of actions that lead to state of known value and then choosing the best sequence.-Search.

•Search algorithm-problem as input and returns the solution in the form of sequence.

•Solution found, action carried out-execution phase.

Learning agents

•It allows the agent to operate in unknown environment.

    4 components:

   1) Learning element.

   2) Performance element.

   3) Critic.

   4) Problem generator.

•Learning element:

    Responsible for making improvements.

•Performance element:

    Responsible for selecting external action. (entire agent)-Percepts and decides on action.

•Critic:

    Learning element uses feedback from critic-how the agent ids doing, how the performance element should be modified to do better in future. 
•Problem generator:

   Responsible for suggesting actions that will lead to new and informative experiences.

Agent types

 

Four basic types in order of increasing generality:

•Simple reflex agents

•Model-based reflex agents

•Goal-based agents

•Utility-based agents

Simple reflex agents:

•Select actions on the basis of the current percept, ignoring the rest of the percept histroy.

•Eg:

    Vacuum agent

• Its decision is based only on the current location and on whether that contains dirt

Model-based reflex agents:

•Partial observability-maintain some sort of internal state,depends on percept history,reflects some unobserved aspect.

    2 kind of knowledge:

 1)How world evolves independently of the agent.

2)How the agent’s own action affect the world.

“How the world works”-Model of the world

Goal-based agents:

            •With current state description, the agent needs goal information.

                 Eg: taxi driving- passenger’s destination.

             •Goal based action is straight forward.

                    “What will happen if I do such and such?”
Utility-based agents:

             •Goal alone are not enough to generate high quality

             •Goal just provide distinction between “happy” and “unhappy”.

                     Two kind of cases where goals are inadequate:

                          •  Conflicting goals-some of them can be achieved.

                          •Several goals-none can be acieved,importance of goals are taken.