Planning in Artificial Intelligence (Unit-3rd)

Planningand Learning:

Neuronpresent in our brain is responsible for thinking.

 

NeuralNetwork (Artificial Network):

            AnAI neural network is a system based on the biological neural n/w. In otherwords, it is an immolation of biological neural system. Although, computing innow a day is truly advanced. There are certain task that a program made for acommon microprocessor is able to perform

even so,  a s/w implementation of a neural network canbe made with their advantage and dis-advantages.

Advantages:

1.    A neural network can perform tasks that a linear programmer cannot.

2.   It can be implemented in any application.

3.   A neural n/w learns and don’t need to re-programmed.

4.  When an element of the neural network fails, it can continue withoutany problem by their parallel nature.

Disadvantage:

1. The neural network needs training to operate.

2. The architecture of neural network is different from the architectureof microprocessor, so need to be emulated.

3. It requires high processing time for last neural network.

Planning:

            Intelligentagents must be able to set goals and achieve them. They need a way to visualizethe future and be able to make choices that maximize the utility if availablechoices. In classical planning problems, the agents can assume that it is theonly thing acting on the world, and it can be certain about what the certainconsequences of its action may be.

However, if this is not true, it must periodicallycheck if the world make its predictions & it must change its plan as thisbecome necessary requiring the agent to reason under uncertainty.

            Planningis finding a sequence of operator that transforms an initial state into a goalstate. Planning is the representation of state, action and goal. Researches inAI have studied planning for many years and many techniques exist forautomating planning process.

The issue include:

1.    How to represent action and the world state.

2.    How to represent the time.

3.    How to dynamically combine planning and execution.

Specified planning techniques means and analysis, linearand non-linear planning, partial order planning, heuristic planning,conditional planning.

Initial state ->> Action ->> Goal->> Plan.

Planning insituational calculus:

            Situationalcalculus is predicate calculus, formalization of states, action and effect ofactions on states. Planning is formalized as asking question like “Does theirexist a state that it satisfy the goal ?”

            Resolutiontheorem applied is to solve the problem, situations are connected by the resultfunction i.e.

            SI=Result (a,S) is a function giving the situation that result from ding action“a” while the situation is “S”.

Consider the task, Get milk, banana, and a code-lessdrill:-

1. Initial State: is at (Home, S)  /\ Have ( milk, S)  /\  Have (banana, S) …….

2. Action: Have (milk, Result (a,S)) <=>[(a=buy (milk) /\ at super market) /\ (Have milk,S) /\ a != drop (milk)]

3. Query: There exist-

                        Forall p(S)= plan result (p,S) /\ at (home,S) /\ have(milk,S) /\ have(banana, S)/\.....

4. Bounded vars: variables which are with for all,and there exist notations. Else all are free variables.

Solution:

p=[Go (supermarket),buy(milk), buy(banana), Go(hardware shop), buy(drill), ……]

Representationof Plans:

            Aplan is formally defined as data structure consisting of following 4components-

1.    A set of plan steps.

2.    A set of step ordering constraints.

3.    A set of var binding constraints.

4.    A set of casual links.

Key difference between plan space planning andsituation space planning:- In situation space planners, all specs are vars& all ordering must be fixed when each operation is applied.

            Whilein plan space planners make commitments only as necessary. Hence plan spaceplanners are least commitment plans.

PartialOrder Planning:

1.    Basic idea: Search in plan space and use least commitment whenpossible.

2.    Plan Space search: Search space is set of partial plans, Plan is tuple where  A is set of actions,o is set of ordering, B is set of binding.

3.    Initial Plans: <{Start, Finish} {start, finish}>

a.    Start has no pre-condition, its effect are initial state.

b.    Finish has no effect, its pre-condition is goal.

4.    Least Commitments:

a. Basic Idea: Make choices that are relevant to solve the current part ofproblem.

b. Least commitment choices:

                       i. Ordering: Leave action unordered unless they must be sequential.

              ii. Binding: Leave vars unbound unless needed to unified with conditionsbeing achieved.

                       iii. Actions: Usually not subjected to least commitment.

c.  Refinment:

                       i. Only add info to the current plans.

                       ii. Transformational planning can remove choices.

PlanTerminology:

1. Totally ordered Plan: there exist sufficient ordering ‘O’ such that allaction is ‘A’ are ordered with respect to each other.

2. Fully instantaneous Plans: there exist sufficient constraint in ‘B’such that all vars are constraint to the equal to some constant.

3. Consistent Plan: there is no contradiction in ‘O’ or ‘B’.

4. Complete Plan: every prediction ‘P’ of every AI action in ‘A’ isachieved.

There exist an effect of anaction ‘aj’ that comes before AI and unifies with ‘P’ & no action AK thatdetects ‘P’ comes between aj and AI.

Advantageand dis-advantage of POP:

Advantages:

1.    POP os sound and complete.

2.    Typically procedure optimal solution i.e plan length.

3.    Least commitment may lead to shorter time search.

Dis-advantages:

1.    Significantly more complex algo’s (higher per node cost)

2.    Hard to determine what is true in state.

3.    Large search spaces since concurrent action are a lot.

** Stay connected for notes on Learning in Artificial Intelligence and more...