Problem Defining and Solving Problem

Problem Defining and Solving Problem

AU: Dec.-10

What is Problem Solving?

For solving any type problem (task) in real world one needs formal description of the problem.

One should have clear undenstanding of following aspects of the problem →

1. What is the Explicit Goal of the Problem

Goals help to organize behaviour of systems by limiting the objectives that the agent is trying to achieve. Goal formulation is based on the current situation and the agent's performance measure. It is first step towards problem solving.

2. What is Implicit Criteria for Success

That is how success is defined. That will be the ultimate thing system needs to achieve, which is the problem solution's output.

3. What is the Initial Situation

It means that what is going to be the start state of problem being solved.

4. Ability to Perform

It tells how agents transforms from one situation to another, how operations and rules are specified which change the states of the problem during solution process.

Well Defined Problems

Problem formulation is the process of deciding what actions and states to consider, given a goal.

A problem can be defined formally by four components.

1) Initial state that the agent starts in

For example –

Consider a agent program Indian Traveller developed for travelling from Pune to Chennai travelling through different states. The initial state for this agent can be described as In (Pune).

2) A description of the possible actions available to the agent

The most common formulation uses a successor funtion. Given a perticular state x, SUCCESSOR Function (X) returns a set of <action, successor>, ordered pairs, where each action is one of the legal actions in state x and each successor is a state that can be reached from x by applying the action.

For example:

From the state In (Pune), the successor function for Indian Traveller problem wouldreturn.

{

< Go (Mumbai), In (Mumbai) >

< Go (AhemdNagar), In (AhemdNagar)>

< Go (Solapur), In (Solapur)>

< Go (Satara), In (Satara)>

}

Together, the initial state and successor function implicitly define the state space of the problem - which is the set of all states reachable from the initial state.

The state space forms a graph in which the nodes are states and the arcs between nodes are actions.

A path is the state space is a sequence of states connected by a sequence of actions.

3) The goal test, which determines whether a given state is goal (final) state. In some problems we can explicitely specify a set of goals. If a particular state is reached we can check it with set of goals and if a match is found success can be announced.

For example:

In Indian Traveller problem the goal is to reach chennai i.e. it is a singleton set {In (Chennai)}.

In certain types of problems we can not specify goals explicitly. Instead, goal is specified by an abstract property rather than an explicitly enumerated set of states.

For example:

In chess, the goal is to reach a state called "Checkmate" where the opponent's king is under attack and can not escape. This "Checkmate" situation can be represented using various state spaces.

4) A path cost function that assigns a numeric cost (value) to each path. The problem-solving agent is expected to choose a cost-function that reflects its own performance measure.

For Indian-Traveller agent we can have time requireded as cost for path-cost function. It should consider length of each road being travelled.

In general step-cost of taking action 'a' to go from state x to state c (x, a, y).

The above four elements define a problem and can be put together in single data structure which can be given as input to a problem-solving algorithm.

A solution to the problem is a path from the initial state to a goal state.

We can measure quality of solution by the path cost function. We can have multiple solutions to the problem. The optimal solution will be the one with lowest path cost among all the solutions.

Problem Formulation Types

There are two main kinds of problem formulation ⇒

1) Incremental formulation

2) Complete-state formulation.

Depending upon problem requirements and specification one can decide which onegofor.

1) Incremental formulation

• It involves operators that augment the state description, starting with an empty state.

• It generates many sequences.

• Memory requirements is less as all states are not explored (exploration will be done till the goal is found).

For example-

For the 8-queens problem, incremental formulation states that, each action adds a queen to the state. In this formulation we have 64.63 ... 57 3×1014 possible sequences to investigate.

2) Complete state formulation

• In this initially we will have some basic configuration represented in initial state.

• Here while doing any action first the conditions on the actions will be checked so that the configuration state after the action will be same legal state.

• It takes up large memory as complete state space is generated. This formulation reduces number of sequences generated.

For example-

In 8-queen problem initially all the queens will be arranged on the board. The action will be 'move a queen to the next square such that it is not attacking'.

This complete state formulation reduces state space from 3×1014 (which is for incremental formulation) to just 2,057 and solutions are easy to find.

Example of incremental formulation and complete-state formulation:

Consider 8-queen problem,

• Incremental formulation

1) States

-Arrangement of upto 8 queens on the board.

2) Initial state

- Empty board.

3) Successor function (operators)

- Add a queen to any square.

4) Goal test

- All queens on board

- No queen attacked.

Properties: 3×10¹⁴ possible sequences.

• Complete state formulation

1) States.

-Arrangement of 8-queens on the board.

2) Initial state

-All 8 queens on board.

3) Successor function (operators)

- Move a queen to a different square.

4) Goal test

- No queen attacked.

Properties: Good strategies can reduce the number of possible sequences which are considerable.

Solving the Problem

Finding the solution of a problem is procedure which involves following phases←

1) Problem definition: Where in detailed specification of inputs and what constitutes an acceptable solution is described.

2) Problem analysis: Where in problem is studied through various view points like inputs, to the problem, environment of the problem, expected outputs.

3) Knowledge representation: Where in the known data about the problem and various expected stimuli from environment is represented in perticular format which is helpful for taking actions.

4) Problem solving: Where in the selection of best suited techniques for problem solutions are thought of and finalized.

Problem Solving Agents

1. Approach of Problem Solving Agent

Goal based agents are also called as problem solving agent.

Problem solving agent adapt to the task environment understand goal and achieve success -

Problem solving agents determine sequence of actions which generate successful state. Problem solving agent can be aimed at maximizing performance measure there by developing intelligent problem solving agent.

2. Steps in Problem Solving

Problem solving agent achieves success by taking following approach to problem solution -

Step 1: Goal setting

Agent set the goal by considering the environment.

Step 2: Goal formulation

The goals set in step 1 are formalized in the frame work. The key activity in goal formulation is

1) To observe current state. 2) To tabulate agents performance measures.

Step 3: Problem formulation

After formulating goal, it is required to find out what will be the sequence of actions which generate goal state.

Problem formulation is a way of looking at actions and states generated because of actions, which leads to success.

Step 4: Search in unknown environment

If the task environment is unknown then agent first tries different sequence of actions and gathers knowledge (i.e. learning). Then agent gets known set of actions which leads to goal state. Thus agent search for describable sequence of actions this process is called as searching process.

With knowledge of environment and goal state we can design a search algorithm. A search algorithm is a procedure which takes problem as input and return its solution which represented in the form of action sequence.

Step 5: Execution phase

Once the solution is given by the search algorithm then the actions suggested by the algorithm are executed. This is the execution phase. Solution guides agent for doing the actions. After executing the actions agent again formulate new goal.

3. Algorithm

Procedure or method: Problem solving agent (unknown space, percept).

Results: An action.      

Input: P→ percept (Environment perception)

Static:

1) A → An action sequence, initially with null value.

2) S→ State-current state.

3) G→ Goal - A goal initially null.

4) P→ Problem - A real world situation.

State- update state (State, percept)

If (s) is empty then do

g← Formulate goal (s)

P← Formulate problem (s, g)

S← Search (p)

G← First (s)

S← Rest (s)

Return a

Procedure

4. Example of Problem Solving Agent

Consider following simple problem solving agent. Working in open-loop system. Open-loop system means agent is assumed to be working in following environment -

1) Static environment: Where in problem formulation and solution is done by ignoring the changes that can occur in environment.

2) Observable environment: Where in agent has complete knowledge of environment.

3) Discrete environment: Where in the idea of enumerating "alternative courses of actions" is implemented.

4) Deterministic environment: Where in next state is configured from current state.

• Points to Note

1) Above kind of working systems is called as open-loop system, because ignoring the percepts breaks loop between agent and environment.

2) In open-loop systems solutions to problem are single sequence of actions, so they cannot handle any unexpected events.

3) Also solutions are executed without paying attention to the percepts.

4) These are most easiest kind of environment to work in for agents.