Artificial Intelligence Unit 4-Artificial Intelligence PDF

Preview

Summary

UNIT – 4####### What is planning in AI? The planning in Artificial Intelligence is about the decision making tasksperformed by the robots or computer programs to achieve a specific goal. The execution of planning is about choosing a sequence of actions with a highlikelihood to complete the specifi...

Description

UNIT – 4 What is planning in AI? 

The planning in Artificial Intelligence is about the decision making tasks performed by the robots or computer programs to achieve a specific goal.



The execution of planning is about choosing a sequence of actions with a high likelihood to complete the specific task.

Components of Planning System The planning consists of following important steps: 

Choose the best rule for applying the next rule based on the best available heuristics.



Apply the chosen rule for computing the new problem state.



Detect when a solution has been found.



Detect dead ends so that they can be abandoned and the system’s effort is directed in more fruitful directions.



Detect when an almost correct solution has been found.

Goal stack planning This is one of the most important planning algorithms, which is specifically used by STRIPS. 

The stack is used in an algorithm to hold the action and satisfy the goal. A knowledge base is used to hold the current state, actions.



Goal stack is similar to a node in a search tree, where the branches are created if there is a choice of an action.

Example : Blocks-World planning problem 

In blocks-world problem, three blocks labeled as 'A', 'B', 'C' are allowed to rest on the flat surface. The given condition is that only one block can be moved at a time to achieve the goal.



The start state and goal state are shown in the following diagram.

The important steps of the algorithm are as stated below: i. Start by pushing the original goal on the stack. Repeat this until the stack becomes empty. If stack top is a compound goal, then push its unsatisfied subgoals on the stack. ii. If stack top is a single unsatisfied goal then, replace it by an action and push the action’s precondition on the stack to satisfy the condition. iii. If stack top is an action, pop it from the stack, execute it and change the knowledge base by the effects of the action. iv. If stack top is a satisfied goal, pop it from the stack. S.No 1

Functions Pickup(X)

Pre-Condition Arm empty On(X,Table) Clear(X)

Action Holding(X)

2

Putdown(X)

Holding(X)

Arm empty On(X,Table) Clear(X)

3

Stack(X,Y)

Holding(X) Clear(Y)

On(X,Y) Clear(X) Arm empty

4

UnStack(X,Y)

On(X,Y) Clear(X) Arm empty

Holding(X) Clear(Y)

Note- X and Y are blocks on table Example: Start State

:

A

B

A B

Goal State :

Write start sate in Logical Way: i.e.

On(A,Table)

and On(B,Table)

Similarly Goal State can be written as i.e. On(A,B)

So to get On(A,B) , the suitable function is Stack(A,B) and the Precondition for this Holding(A) and Clear(B). So we have to check on current state whether pre-condition is holding or not. So Is my arm Holding(A) : NO Clear(B)

: YES

So, First we have to make Holding(A) is True. To make this true we apply function PickUP(A). For this we have to check the precondition for PickUP(A). is satisfied or not and these preconditions are: Arm empty

: YES

On(A,Table) : YES

Clear(A)

: YES

Because all precondition are satisfied so we can do PickUP(A).

So when we do PickUP(A) then Holding(A)

become true.

Now both precondition for Stack(A,B) is satisfied so we can do Stack(A,B). And we get Goal state.

Non-linear planning This planning is used to set a goal stack and is included in the search space of all possible subgoal orderings. It handles the goal interactions by interleaving method. Advantage of non-Linear planning Non-linear planning may be an optimal solution with respect to plan length (depending on search strategy used). Disadvantages of Nonlinear planning



It takes larger search space, since all possible goal orderings are taken into consideration.



Complex algorithm to understand. Algorithm 1. Choose a goal 'g' from the goalset 2. If 'g' does not match the state, then



Choose an operator 'o' whose add-list matches goal g



Push 'o' on the opstack



Add the preconditions of 'o' to the goalset 3. While all preconditions of operator on top of opstack are met in state



Pop operator o from top of opstack



state = apply(o, state)



plan = [plan; o]

Hierarchical planning Hierarchical planning is also called as plan decomposition. Generally plans are organized in Hierarchical format. Pop one level planner: If you are planning to take a trip, then first you have to decide the location. To decide location we can search for various good locations from internet based on, whether conditions, travelling expenses, etc. This is level one planning. Hierarchy of actions: In terms of major and minor or actions, hierarchy of actions can be decided. Minor activities would cover more precise activities to accomplish the major activities. Major steps are given more importance. Once major steps are decided we attempt to solve the minor detailed actions.

Planner: i. First identify a hierarchy of major conditions. ii. Construct a plan in levels. iii. Patch major level details. iv. Finally demonstrate

Partial-order planning Partial-order planning is an approach to automated planning that maintains a partial ordering between actions and only commits ordering between actions when forced to i.e., ordering of actions is partial. Also this planning doesn't specify which action will come out first when two actions are processed. By contrast, total-order planning maintains a total ordering between all actions at every stage of planning. Given a problem in which some sequence of actions is required in order to achieve a goal, a partial-order plan specifies all actions that need to be taken, but specifies an ordering between actions only where necessary.

Consider the following situation: a person must travel from the start to the end of an obstacle course. This obstacle course is composed of a bridge, a see-saw and a swing-set. The bridge must be traversed before the see-saw and swing-set are reachable. Once reachable, the see-saw and swing-set can be traversed in any order, after which the end is reachable. In a partial-order plan, ordering between these obstacles is specified only when necessary. The bridge must be traversed first. Second, either the see-saw or swing-set can be traversed. Third, the remaining obstacle can be traversed. Then the end can be traversed. Partialorder planning relies upon the Principle of Least Commitment for its efficiency.

Partial-order plan A partial-order plan or partial plan is a plan which specifies all actions that need to be taken, but only specifies the order between actions when necessary. It is the result of a partial-order planner. A partial-order plan consists of four components:   



A set of actions (also known as operators). A partial order for the actions. It specifies the conditions about the order of some actions. A set of causal links. It specifies which actions meet which preconditions of other actions. Alternatively, a set of bindings between the variables in actions. A set of open preconditions. It specifies which preconditions are not fulfilled by any action in the partial-order plan.

In order to keep the possible orders of the actions as open as possible, the set of order conditions and causal links must be as small as possible. A plan is a solution if the set of open preconditions is empty. A linearization of a partial order plan is a total order plan derived from the particular partial order plan; in other words, both order plans consist of the same actions, with the order in the linearization being a linear extension of the partial order in the original partial order plan.

Example For example, a plan for baking a cake might start:    

go to the store get eggs; get flour; get milk pay for all goods go to the kitchen

This is a partial plan because the order for finding eggs, flour and milk is not specified, the agent can wander around the store reactively accumulating all the items on its shopping list until the list is complete.

What is learning? 

According to Herbert Simon, learning denotes changes in a system that enable a system to do the same task more efficiently the next time.



Arthur Samuel stated that, "Machine learning is the subfield of computer science, that gives computers the ability to learn without being explicitly programmed ".



In 1997, Mitchell proposed that, " A computer program is said to learn from experience 'E' with respect to some class of tasks 'T' and performance measure 'P', if its performance at tasks in 'T', as measured by 'P', improves with experience E ".



The main purpose of machine learning is to study and design the algorithms that can be used to produce the predicates from the given dataset.



Besides these, the machine learning includes the agents percepts for acting as well as to improve their future performance. The following tasks must be learned by an agent.



To predict or decide the result state for an action.



To know the values for each state(understand which state has high or low vale).



To keep record of relevant percepts.

Why do we require machine learning? 

Machine learning plays an important role in improving and understanding the efficiency of human learning.



Machine learning is used to discover a new things not known to many human beings. Various forms of learnings are explained below: 1. Rote learning Rote learning technique avoids understanding the inner complexities but focuses

on memorizing the material so that it can be recalled by the learner exactly the way it read or heard. Learning by memorization: which avoids understanding the inner complexities the subject that is being learned. Learning something from Repeating:saying the same thing and trying to remember how to say it;it does not help to understand ,it helps to remember ,like we learn a poem,song ,etc. 

Rote learning is possible on the basis of memorization.



This technique mainly focuses on memorization by avoiding the inner complexities. So, it becomes possible for the learner to recall the stored knowledge. For example: When a learner learns a poem or song by reciting or repeating it, without knowing the actual meaning of the poem or song. 2. Induction learning (Learning by example).



Induction learning is carried out on the basis of supervised learning.



In this learning process, a general rule is induced by the system from a set of observed instance.



However, class definitions can be constructed with the help of a classification method. For Example: Consider that 'ƒ' is the target function and example is a pair (x ƒ(x)), where 'x' is input and ƒ(x) is the output function applied to 'x'. Given problem: Find hypothesis h such as h ≈ ƒ



So, in the following fig-a, points (x,y) are given in plane so that y = ƒ(x), and the task is to find a function h(x) that fits the point well.



In fig-b, a piecewise-linear 'h' function is given, while the fig-c shows more complicated 'h' function.



Both the functions agree with the example points, but differ with the values of 'y' assigned to other x inputs.



As shown in fig.(d), we have a function that apparently ignores one of the example points, but fits others with a simple function. The true/ is unknown, so there are many choices for h, but without further knowledge, we have no way to prefer (b), (c), or (d).

3. Learning by taking advice



This type is the easiest and simple way of learning.



In this type of learning, a programmer writes a program to give some instructions to perform a task to the computer. Once it is learned (i.e. programmed), the system will be able to do new things.



Also, there can be several sources for taking advice such as humans(experts), internet etc.



However, this type of learning has a more necessity of inference than rote learning.



As the stored knowledge in knowledge base gets transformed into an operational form, the reliability of the knowledge source is always taken into consideration.

Explanation based learning 

Explanation-based learning (EBL) deals with an idea of single-example learning.



This type of learning usually requires a substantial number of training instances but there are two difficulties in this: I. it is difficult to have such a number of training instances ii. Sometimes, it may help us to learn certain things effectively, specially when we have enough knowledge. Hence, it is clear that instance-based learning is more data-intensive, datadriven while EBL is more knowledge-intensive, knowledge-driven.



Initially, an EBL system accepts a training example.



On the basis of the given goal concept, an operationality criteria and domain theory, it "generalizes" the training example to describe the goal concept and to satisfy the operationality criteria (which are usually a set of rules that describe relationships between objects and actions in a domain).



Thus, several applications are possible for the knowledge acquisition and engineering aspects.

Learning in Problem Solving 

Humans have a tendency to learn by solving various real world problems.



The forms or representation, or the exact entity, problem solving principle is based on reinforcement learning.



Therefore, repeating certain action results in desirable outcome while the action is avoided if it results into undesirable outcomes.



As the outcomes have to be evaluated, this type of learning also involves the definition of a utility function. This function shows how much is a particular outcome worth?



There are several research issues which include the identification of the learning rate, time and algorithm complexity, convergence, representation (frame and qualification problems), handling of uncertainty (ramification problem), adaptivity and "unlearning" etc.



In reinforcement learning, the system (and thus the developer) know the desirable outcomes but does not know which actions result into desirable outcomes.



In such a problem or domain, the effects of performing the actions are usually compounded with side-effects. Thus, it becomes impossible to specify the actions to be performed in accordance to the given parameters.



Q-Learning is the most widely used reinforcement learning algorithm.



The main part of an algorithm is a simple value iteration update. For each state 'S', from the state set S, and for each action, a, from the action set 'A', it is possible to calculate an update to its expected reduction reward value, with the following expression: Q(st, at) ← Q(st, at) + αt (st, at) [rt + γmaxaQ (st+1, a) - Q(st, at)]



where rt is a real reward at time t, α t(s,a) are the learning rates such that 0 ≤ αt(s,a) ≤ 1, and γ is the discount factor such that 0 ≤ γ < 1.

Problem-based learning Problem-based learning (PBL) is a student-centered pedagogy in which students learn about a subject through the experience of solving an open-ended problem found in trigger material. The PBL process does not focus on problem solving with a defined solution, but it allows for the development of other desirable skills and attributes. This includes knowledge acquisition, enhanced group collaboration and communication. The PBL process was developed for medical education and has since been broadened in applications for other programs of learning. The process allows for learners to develop skills used for their future practice. It enhances critical appraisal, literature retrieval and encourages ongoing learning within a team environment.

The PBL tutorial process involves working in small groups of learners. Each student takes on a role within the group that may be formal or informal and the role often alternates. It is focused on the student's reflection and reasoning to construct their own learning. The Maastricht seven-jump process involves clarifying terms, defining problem(s), brainstorming, structuring and hypothesis, learning objectives, independent study and synthesis. In short, it is identifying what they already know, what they need to know, and how and where to access new information that may lead to the resolution of the problem. The role of the tutor is to facilitate learning by supporting, guiding, and monitoring the learning process.The tutor aims to build students' confidence when addressing problems, while also expanding their understanding. This process is based on constructivism. PBL represents a paradigm shift from traditional teaching and learning philosophy, which is more often lecture-based. The constructs for

teaching PBL are very different from traditional classroom or lecture teaching and often require more preparation time and resources to support small group learning.

Advantages There are advantages of PBL. It is student-focused, which allows for active learning and better understanding and retention of knowledge. It also helps to develop life skills that are applicable to many domains. It can be used to enhance content knowledge while simultaneously fostering the development of communication, problem-solving, critical thinking, collaboration, and self-directed learning skills. PBL may position students to optimally function using real-world experiences. By harnessing collective group intellect, differing perspectives may offer different perceptions and solutions to a problem. Following are the advantages and limitations of problem-based learning. Enhance student-centred learning In problem-based learning the students are actively involved and they like this method.It fosters active learning, and also retention and development of lifelong learning skills. It encourages self-directed learning by confronting students with problems and stimulates the development of deep learning. Upholds lifelong learning Problem-based learning gives emphasis to lifelong learning by developing in students the potential to determine their own goals, locate appropriate resources for learning and assume responsibility for what they need to know. It also greatly helps them better long term knowledge retention. In-depth learning and constructivist approach PBL fosters learning by involving students with the interaction of learning materials. They relate the concept they study with everyday activities and enhance their knowledge and understanding. Students also activate their prior knowledge and build on existing conceptual knowledge frameworks.

Augments self-learning Students themselves resolve the problems that are given to them, they take more interest and responsibility for their lea...