Home Classroom Artificial Intelligence

Informed Search Strategies

In the last article on Artificial Intelligence which appeared on diGIT’s June 2010 issue, we discussed about different types of ‘Informed search’ strategies. Just to recall, this type of searching uses extra problem-specific knowledge which is beyond the actual problem itself in finding the best solution. It is said that informed search leads to finding better problem-specific solutions in an efficient manner when compared to the uninformed search. You might also remember that we have another name for this search known as ‘Heuristic search’. Last time we mainly discussed about two types of searches called the ‘Greedy Best-First Search’ and ‘A* Search’. Please read the last article to get more information about these if you have forgotten what they are all about.

Today, we would be discussing about some other heuristic search strategies available and also would try to understand about heuristic functions and how they can be constructed.

Types of Informed Search Continued
1. Best-First Search
  • a. Greedy best-first Search
  • b. A* Search

The above search strategies were discussed in the previous article.

2. Memory bounded heuristic search

As the name implies, this type of search tries to reduce the memory requirements while searching based on heuristics. With regard to A* search which we briefly described last time, one of its main drawbacks is the high amount of memory consumption. It has to keep all generated nodes at each iteration in the memory, so when we run this algorithm on a large scale problem, it will run out of memory causing trouble. Some of such memory-bounded algorithms are described in detail as follows.

a. Iterative-deepening A* search (IDA*)

In general, Iterative-deepening search is a step by step procedure where the problem space is expanded until a certain pre-specified limit has been reached. In the case of A* search the evaluation function is defined as follows.

f(n) = g(n) + h(n)

where;

  • g(n) – cost to reach the node
  • h(n) – cost to each node from the goal node

In this case, when we consider the iterative-deepening A* search the pre-defined limit for the iterative deepening search is an upper limit on the value of the evaluation function (f(n)). In the case where, a node in concern has a comparatively lower f(n) value to the cut-off limit, then that node would be expanded and if the algorithm reaches a node which has a f(n) value exceeding the limit, the algorithm will cease to expand on that node on that particular path and move on to finding other paths to reach the goal node. By imposing this kind of cut-off limit for the evaluation function cost, the nodes which are not feasible to be in the path would not be put on to memory and only the nodes within the paths which are feasible and cost effective would be stored in memory. This would lead to a lower memory requirement than using A* search on its whole.

b. Recursive best-first search (RBFS)

A recursive algorithm is one which calls the same algorithm within itself with different input arguments at each time until a certain objective function has been reached. RBFS is a simple such recursive algorithm which tries to do the operation of standard best-first search (which was explained last time) but using only a limited memory space. In this type of best-first search the evaluation function (f(n)) in concern is the combination of:

  • g(n) – cost to reach the node
  • h(n) – cost to each node from the goal node

RBFS algorithm keeps track of the evaluation function value (i.e. f(n) value) of the best alternative path available from any ancestor of the current node. If the current node’s evaluation function value exceeds this limit, the recursive step makes the algorithm take the alternative path instead. When such recursion occurs, RBFS algorithm replaces the previous f-value of each node along its path with the best f-value of its children. By doing this, the memory requirement is limited, because it does not need to keep all the expanded nodes in memory. It only needs to store the evaluation function values of best alternative path from each ancestor node of the current node and do a comparison with the current value and update it if required, making the memory requirement decrease. Although this looks quite feasible, there is another drawback in RBFS algorithm. That is it uses too little memory and is not capable of utilizing all the available memory if required. So, in another sense, it wastes available memory in a system since this algorithm cannot utilize it but rather use very limited memory to perform its operations. Therefore, some other algorithms have come in to play which use limited memory but also have the ability to utilize all available memory, which are described in detail in the following sections.

c. Simplified Memory-bounded A* search (SMA)

SMA algorithm works quite similar to the general A* search algorithm with the only exception being, it expanding the best leaf only until the memory is full. When it reaches the point of memory being full, it has to drop an existing node in memory to fill in the new one. In order to do this, SMA algorithm follows a simple strategy where it drops the worst leaf node already in memory and adds in the new node. ‘Worst leaf node’ means the leaf node in the memory which has a highest evaluation function value which is f(n), which implies it costs more to expand on that node in order to reach the goal. Therefore, this algorithm removes it and adds the better node in the memory. There might be a scenario where all the leaf nodes have the same f-value. In such as case, how does the SMA algorithm select which node is the worst and which node is the best since same node could be selected for both expansion and deletion? The solution is as follows. SMA* solves this by expanding newest best leaf and deleting oldest worst leaf, which means it deletes the node with the same f-value but was in memory for the longest time and adds the latest node. In this type of SMA search, all the limited amount memory that is available would be used to tackle the problem without wasting any resources.

Heuristic functions

The heuristic function is based on the problem in concern. If the goal of a certain problem is finding the lowest distance path from one place to another, then the heuristic function is obviously the lowest distance from each node to the goal node. The problems in practice are not so simple and obvious most of the time. Therefore, it is essential to know some important aspects that should be considered when coming up with a good heuristic function to do the searching on that problem space. Some important pointers when designing a heuristic function are as follows.

  • It should never overestimate the true solution cost to the goal – For example, if the most feasible path to the goal node from the starting node costs ‘x’ no: of steps, then the heuristic function should not exceed that limit from any node for it to be a suitable heuristic function.
  • The quality of the heuristic mostly depends on the ‘effective branching factor’ value – Following is the definition for effective branching factor. If the total number of nodes generated by A* search for a problem space is N, and the solution tree depth is d, then the effective branching factor b is defined using the following equation

N + 1 = 1 + b + b2 + b3 + … … … … … … . + bd

Therefore after removing 1 from both sides of the equation;

N = b + b2 + b3 + … … … … … … . + bd

The above is a geometric series. So to find the sum of a geometric series the equation is as follows. Hope you all can remember your year 10-11 Mathematics for doing this.

Where r – common ratio, n – no: of terms

Therefore in our equation no: 2 can be re-written as:-

Then an approximate solution for b can be obtained mathematically, which is called the effective branching factor. It is found out that that for a well-designed heuristic, the value for the effective branching factor would be close to 1.

Stay tuned!

Over the past few months and from today’s article, we discussed a lot about searching strategies available in problem solving which is a vital component in Artificial Intelligence. We learnt about problem solving basics, formulation of problems and solutions, uninformed (blind) search strategies and informed (heuristic) search strategies throughout this article series. Hope you were able to gain some understanding and develop an interest towards this area which paves the basics to AI. From the next article onwards, we will be presenting more about new machine learning techniques in AI such as neural networks, classification and clustering and so on. So, stay tuned!

References
Artificial Intelligence – A modern Approach, Second edition, Stuart Russell & Peter Norvig

Artificial Intelligence : Informed search

In the previous article on Artificial Intelligence which appeared on diGIT’s April 2010 issue, we discussed about search strategies for problem solving. There we talked about the main two strategies in search called ‘uninformed search’ and ‘informed search’ and discussed in detail only about ‘uninformed search’. Today we are going to discuss about what is meant by ‘informed search’. As the name implies, it uses problem-specific knowledge in which is beyond the actual problem itself in finding the best solution that problem in hand unlike the previously discussed ‘uninformed search’ where no additional knowledge about the problem has been provided. Informed search leads to finding better problem-specific solutions in an efficient manner when compared to the other search strategy mentioned before. Informed Search is also known as ‘Heuristic search’ which shows that this type of search strategy uses heuristics (cues) about the problem domain to come up with the most suitable solution.

Types of Informed Search
1.Best-First Search

This is a general graph search algorithm. At each node of the graph it should evaluate which node to be expanded next in order to arrive at the optimal solution efficiently. This is achieved by the introduction of an ‘evaluation function’ which evaluates at each point, which node to be expanded next based on the lowest evaluation function result. Usually, the evaluation function mentioned above measures the distance from the node in concern to the goal, so a lower evaluation function is preferred over a higher evaluation function. Another key factor in this search algorithm is called the ‘heuristic function’ which is a part of the evaluation function, which is defined as the ‘cheapest cost of the cheapest path from a node to a goal node’. Therefore, this algorithm chooses the lowest cost paths from the selected best nodes of the graph to arrive at the goal node, leading to the best solution and the heuristic function value would be zero at the goal node, which acts as a stopping condition for the algorithm to terminate when it reaches the goal.

Based on how the ‘evaluation function’ and ‘heuristic function’ is linked together, there can be different variations of the above mentioned ‘Best-First Search’ strategy, which are explained in detail as follows.

1.1.Greedy Best-First Search

This search method expands the node that is closest to the goal node which is likely to lead to a solution in a quick manner. In this case, the ‘heuristic function’ (h(n)) and the ‘evaluation function’ (f(n)) are the same. One can come up with different ‘heuristic functions’ based on the problem domain in concern and apply it.

Here:- f(n) = h(n)

Let’s first consider a small example which consists of distances between cities and where a tourist wants to find the path that he should travel in order to minimize the distance he travels from city ‘A’ to city ‘N’.

The following table shows the distances in kilometers (approximate road distance) from the destination city ‘N’ to each respective city.

From City Road distance (km) From City Road distance (km)
A 450 H 300
B 345 I 320
C 420 J 50
D 350 K 220
E 175 L 75
F 250 M 200
G 280 N 0

Let’s also assume that the existing roads connecting the above cities are as follows.

Now let’s try to see how to perform greedy best-first search to go from city A to city N. So starting from city A, one can go to either city B, H or D according to the above road map.

Since the heuristic is based on expanding the node with the lowest distance, in the above first step, the algorithm would select to go to city H from cist A since it has the lowest road distance. Then it would see which city to move from H.

Since the lowest distance is to city K, it would move to that city next as shown above. Based on the heuristic function of expanding the nodes based on the lowest distance to goal node, this algorithm would move on until it reaches the destination city ‘N’ as shown below.

1.1. A* Search

This is another best-first search strategy which has a different relationship with the evaluation function and the heuristic function when compared to afore explained ‘greedy best-first search’. Here the evaluation function (f(n)) is defined as the combination of cost to reach the node (g(n)) and the cost to each node from the goal node (h(n)).

Here:- f(n) = g(n) + h(n)

Therefore, this search strategy not only uses the heuristic function which consists of distances to each node from the goal node (h(n)) but also uses the path cost (so far travelled cost) from start node to the node in concern (g(n)) in the evaluation. This appears to be a better heuristic which uses the cue that the distance travelled should be minimized along each possible path.

The search continues…..

In this article, we briefly discussed about some informed (heuristic based) search strategies applicable to problem solving. Hope you all got a general idea as to how this strategy is different from the uninformed search strategies described in a previous article and also got a sense of how different heuristic based search strategies work. We would continue to talk about some more heuristic based search strategies and how to come up with heuristic functions to evaluate those in the next article.

AI: Search Strategies for Problem Solving

After a small break in the AI article series, let’s move forward to understanding the next phase of problem solving through searching. Hope our readers can remember the article that appeared in diGIT’s February issue titled ‘Problem solving through Searching’. In that article, I presented the main ideas behind how problem solving in AI. There we went through steps required in problem solving, problem and solution formulation and some real world problems. In today’s article we would look at different ways in which searching can be used to solve problems. We would also look different search strategies available and discuss in detail about one such strategy.

 

Types of Search Strategies

Once we have formulated the problem (as discussed in February article), we have to decide how to find the solutions to those problems. This could be done by searching the state space. If you refer to the section titled ‘Defining Problems and Solution’ in the AI article in February issue, you would be able to refresh your memory about these terms.

When searching for a solution, you have start at the initial state of the search tree/graph and expand each state and visit connected states until the goal state has been reached. There are many ways to determine which state to expand in order to get to the goal state, which are known as ‘Search strategies’. These strategies can be mainly divided in to two groups known as ‘Uninformed search’ and ‘Informed search’ which are described in detail as follows.

  • 1. Uninformed Search – This is also known as ‘Blind Search’. This type of search means that they have no additional information about the states other than the information provided by the problem definition. This type of search can generate successor states and also make a distinction between a goal state and a non-goal state.
  • 2. Informed Search – This type of search strategy is more advanced than uninformed search. It is also known as ‘heuristic search’. This strategy has the ability to determine whether a non-goal state is much better than another non-goal state in arriving at the goal state effectively and efficiently, thus it uses heuristics based information on top of the information provided by the problem definition about the states in the state space.

In today’s article we will focus on uninformed search strategies and then move on to informed search strategies in the next article.

 

Uninformed Search Strategy

As explained above, in this type of search strategy we only have access to information given by the problem definition and there are no additional cues provided. One has to search the given state space expanding on each traversed state until the goal state has been reached. There are many different variations of how uninformed search can be achieved and some of those are explained as follows.

 

1. Breadth-first Search (BFS)

In this type of search, the main idea is that the root node is expanded first and then all the successor states of the root node are expanded afterwards. In the next step the rest of the successor states of the states traversed first would be explored. This activity is continued until the goal state for that specific problem is reached. So, at each state, it is checked whether it is the goal state or not. If we explain the breadth-first search in more specific terms, it requires all the nodes at a given depth of the search tree/graph to be expanded before going to the next depth level of the tree. Following search tree shows how breadth-first traversal works.

Figure 1 – Breadth-first traversal on the state space denoted by a search tree. The root node is ‘A’ and the goal node is ‘F’.

The breadth-first traversal searches the tree in this order as depicted by the red arrows.

 

A->B->C->D->E->F

It is also important to identify the pros and cons of BFS strategy.

Advantages:-

  • This uninformed search strategy can find the goal node where ever it is located in the search tree since it traverses the each node in a breadth-first manner until the goal node is reached. So we call this search strategy to be ‘Complete’ since it always guarantees that it finds the goal node at some level.
  • This finds the goal node is an optimal manner if each of the costs of traversing one node to the other is similar for the entire search tree.

Disadvantages:-

  • Consumes lot of time – For example if the goal node is located at a depth of say 1000 in the tree, it has to traverse all the nodes until the depth 1000 to reach at that goal node which would be computationally very expensive. So BFS is not suitable for complex and large problems with a high order search tree.
  • Consumes lot of space – At each node it expands the nodes connected to it in the next depth level. Therefore, at each iteration it has to keep in memory all the nodes that have visited so far leading to a high requirement of memory. Therefore we can conclude that BFS has a high time complexity and space complexity.

 

2. Uniform-cost Search (UCS)

As the name implies, this search strategy assumes that each of the path costs are equal. This is a simple extension to the BFS search algorithm that we discussed above on a special case when all of the path costs are equal. If the path costs are unequal, then this is exactly identical to BFS.

UCS expands the node with the lowest path cost at each iteration.

 

3. Depth-first Search (DFS)

In the depth-first search (DFS) strategy, there is a clear distinction from the BFS. This always expands the deepest node in the search tree and goes along the depth of each node rather than across the breadth. In figure 2, we have shown how DFS would work on the same search tree as used in illustrating the behavior of BFS.

Figure 2 – Depth-first traversal on the state space denoted by a search tree. The root node is ‘A’ and the goal node is ‘F’.

The depth-first traversal searches the tree in this order as depicted by the blue arrows.

 

A->B->E->F

In this particular scenario, it can be clearly seen that DFS find the goal node in less number of steps when compared to BFS (There can be situations where this would not hold as well).

Let’s now take a look at the advantages and disadvantages of the DFS search strategy.

Advantages:-

  • Better memory requirements – It only needs to store as single path from the root to leaf node, along the remaining unexpanded sibling nodes for each node in the path. Once a node has been traversed, it can be removed from the memory as soon as all its descendent nodes (immediate child and all other descendent nodes from that particular node – for example node B can be removed from memory once nodes E and F are traversed).

Disadvantages:-

  • Does not give an optimal solution – This search strategy might make a wrong choice in the earlier stages of the searching and keep on moving along a very deep path (or even an infinite path) for a long time never realizing that the goal node is not in that path because it does not have heuristics to understand that. Therefore, DFS does not give an optimal solution.
  • Does not give a complete solution – If there is a left sub-tree with no goal node, which spans in depth for a long path, DFS would keep on going down and down never terminating leading to an incomplete solution.

 

4. Depth-limited Search (DLS)

This is a small variation to the general DFS search explained above. Since the DFS search can lead to incomplete solutions due to depth unbounded trees (going down a path forever), depth-limited search ensures that the traversal along the depth of a path is limited to a certain pre-determined depth limit. For example, if we can assume that the goal node should be found within the depth limit of 5 from root node, in this case DLS would go down each path up to depth=5 only and search the tree until it finds the goal node eliminating the infinite-path problem found in general DFS search strategy. The problem with DLS is that it is hard to assume a best pre-determined depth-limit without affecting the solution. A way of finding the nest depth-limit is addressed below in no:5.

 

5. Iterative Deepening & DFS

This is another search strategy usually used as a combination with DFS which helps in finding the best depth-limit (which can be useful for applying depth-limited search). It starts off with depth=0 (only having the root node) and then gradually increasing the depth at each iteration until the goal node has been reached. This strategy tries to combine the good features of both BFS and DFS. As in DFS, its memory requirements are less and like BFS it is a complete algorithm given the branching factor from each node is a finite number and the path cost is a non-decreasing function of the depth of the node. This method is preferred for large search problems since it combines all the goodness of both BFS and DFS and tries to strike a balance between them allowing for better memory requirements and complete and optimal solution finding.

 

6. Bidirectional Search

Another type of uninformed search is called ‘bidirectional search’. As the name implies, it means running two simultaneous searches one starting from the root node (initial state) and the other starting from the goal node. In this case, the search starting from the initial state moves forward along the search tree while the other starting from the goal node moves backward until both the search runs meet at a single node in the middle.

 

Comparison between Uninformed Search Strategies

The following table shows a comparison between all the uninformed search strategies that we discussed throughout this article in terms of time and space complexities and also in terms of solution optimality and completeness. It would give you a clear idea as to how comparable each search strategy is to the others and also you can get the feeling that Iterative deepening and bidirectional search has goodness of all, although in practice they are hard to be implemented.

b – Branching factor of each node (how many branches are created from each node of the search tree) For example, if the search tree is a binary tree, then the branching factor of each node is equal to 2.

d – Depth of the shallowest solution (the depth of the place where the goal node is located form the root node)

m – Maximum depth of the search tree

l – Limited depth of the search tree used in depth-limited search

C* – Cost of the optimal solution (based on path cost)

E – Cost of every action

 

Next in Line

Today we looked different search strategies used in problem solving in AI. We focused on understanding various methods used in uninformed search strategies and discusses the pros and cons, features of each approach and they time and space complexities. In the next article, I would be explaining about the other main search strategy which is called the informed search based on additional heuristics.

References

Artificial Intelligence – A modern Approach, Second edition, Stuart Russell & Peter Norvig

Last month, we looked at how to link different environments to agents, agent functions and agent programs. Now, moving forward in the area of intelligent agents let’s understand what are the different agent types and how they differ from each other type in today’s article. There are mainly five different types of agents which we can group most of the intelligent agents found nowadays. We would start off with the simplest type and go on to define the most sophisticated agent type which is ultimately the most desired type of agents in the context of the real life.

 

1.Simple reflex agents

This the simplest type of agent architecture possible. The underlying concept is very simple and lacks much intelligence. For each condition that the agent can observe from its sensors based on the changes in the environment in which it is operating in, there is a specific action(s) defined by an agent program. So, for each observation that it receives from its sensors, it checks the condition-action rules and find the appropriate condition and then performs the relevant action defined in that rule using its actuators. This can only be useful in the cases that the environment in fully observable and the agent program contains all the condition-action rules possible for each observance, which is somewhat not possible in real world scenarios and only limited to toy simulation based problems. Figure 1depicts the underlying concept in such a simple reflex type agent.

Figure 1 – Simple reflex agent

In the above case, the agent program contains a look-up table which has been constructed prior to the agent being functional in the specific environment. The look-up table should consist of all possible percept sequence mappings to respective actions. (In the case you require to refresh your memory about the concept of look-up table, please refer the last month’s article where there is a last section describes it in detail). Thus based on the input that the agent receives via the sensors (about the current state of the environment), the agent would access this look-up table and retrieve the respective action mapping for that percept sequence and inform its actuators to perform that action. This process is not very effective in a scenario where the environment is constantly changing while the agent is taking the action because, the agent is acting on a percept sequence that it acquired previously to the rapid change in the environment and therefore the performed action might not suit the environment’s state after the change.

 

2.Model based reflex agents

This is a more improved version of the first type of agents with the capability of performing an action based on how the environment evolves or changes from the current state. As in all agent types, model based reflex agents also acquire the percepts about the environment through its sensors. These percepts would provide the agent with the understanding of what the environment is like now at that moment with some limited facts based on its sensors. Then the agent would update the internal state of the percept history and thus would yield some unobserved facts about the current state of the environment. To update the internal state, information should exist about how the world (environment) evolves independently of the agent’s actions and information about how the agent’s actions eventually affect the environment. This idea about incorporating the knowledge of evolvement of the environment is known as a model of the world. This explains how the name Model based was used for this agent type.

Figure 2 –Model based reflex agent

The above diagram shows the architecture of a Model based reflex agent. Once the current percept is received by the agent through its sensors, the previous internal state stored in its internal state section in connection with the new percepts determines the revised description about the current state. Therefore, the agent function updates its internal state every time it receives a new percept. Then based on the new updated percept sequence based on the look-up table’s matching with that entry would determine what action needs to be performed and inform the actuators to do so.

 

3.Goal based agents

This agent is designed so that it can perform actions in order to reach a certain goal. In any agent the main criteria is to achieve a certain objective function which can in layman’s terms referred to as a goal. Therefore, in this agent type goal information is defined so that is can determine which suitable action or actions should be performed out of the available set of actions in order to reach the goal effectively. For example, if we are designing an automated taxi driver, the destination of the passenger (which would be fed in as a goal to reach) would provide him with more useful insight to select the roads to reach that destination. Here the difference with the first two types of agents is that it does not have hard wired condition-action rule set thus the actions are purely based on the internal state and the goals defined. This sometimes might lead to less effectiveness, when the agent does not explicitly know what to do at a certain time but it is more flexible since based on the knowledge it gathers about the state changes in the environment, it can modify the actions to reach the goal.

Figure 3 –Goal based agent

 

4.Utility based agents

Goals by themselves would not be adequate to provide effective behavior in the agents. If we consider the automated taxi driver agent, then just reaching the destination would not be enough, but passengers would require additional features such as safety, reaching the destination in less time, cost effectiveness and so on. So in order to combine goals with the above features desired, a concept called utility function is used. So based on the comparison between different states of the world, a utility value is assigned to each state and the utility function would map a state (or a sequence of states) to a numeric representation of satisfaction. So, the ultimate objective of this type of agent would be to maximize the utility value derived from the state of the world. The following diagram depicts the architecture of a Utility based agent.

Figure 4 –Utility based agent

 

5.Learning agents

In the study of AI, we are mostly interested in finding ways of mimicking human behavior or intelligent in agents. Learning is one of the major areas where human intelligence is based upon. Therefore, it is important to see how we can incorporate learning in the intelligent agents to achieve a certain task more effectively. This type of learning agents has four conceptual components built in. One is the learning element which is the component responsible for making improvements to the existing knowledge. The second component is the critic which gives the feedback to the learning element based on the defined performance standard. First the agent’s sensors input the precept sequence received from its sensors to the critic, which would provide some feedback based on the received percept sequence and the performance standard required to achieve. The third element is the performance element which is responsible for handling and determining the external actions to be performed by the actuators of the agent. This part interacts with the learning element to and ultimately determines what action to perform based on the evolved knowledge. The other component is called the problem generator whose job is to propose actions that would lead to new and informative experiences. This helps the agent to explore beyond the usual horizon and try out new actions which would let it learn more knowledge. In the long run, the learning components which act together and interact would be able to know what actions are better and what actions are worse based on the environment and eventually would lead to improves overall performance. The typical structure of a learning agent is shown in figure 5.

Figure 5 –Learning agent

 

Wrapping up

In today’s article we discussed about the various types of agents that can be built to achieve a certain task. Starting off with simple reflex agents we went in to more complex ideas and complex structures in learning agents. I hope you got some idea about the different types of agents that can be built and it would be worthy to know that it is not required always to construct the most complex structure. In some simple domains, the less complex agent types would be able to perform well, although in real life scenarios the emphasis should be with learning agents. In the next article we would talk a little bit more about agents are then move on to problem solving through searching which is one of the key topics in AI problems. Hope you all enjoyed reading the article series on AI and have developed an interest in this field throughout the year of 2009. We hope you would be looking forward to the continuation of this article series in the coming year as well. Best wishes for a Merry Christmas and Happy New Year!!!!

 

References

Artificial Intelligence – A modern Approach, Second edition, Stuart Russell & Peter Norvig

Moving ahead with Intelligent Agents

In the last article, we discussed about the basics of intelligent agents, rational agents, PEAS structure and about different environment types in which agents can work on. So moving ahead on the same topic on intelligent agents, we would try to understand how to choose an environment for specific agent type, what is meant by an agent function, designing agent programs and also about different types of agents. As I mentioned last time it is quite important that you understand the fundamentals of intelligent agents which was presented in the last month’s article in order to grasp what we talk today. So in case you missed the reading the previous article on intelligent agents, I strongly recommend you to take some time and do read it from diGIT’s last month archive before going through today’s article.

 

Linking environment types to different agents

Last time I gave a small exercise for you at the end of the article to reason on why the following agents are linked to such environment types. Hope you all had a look in to it. Today I would explain the reasoning behind each of it, in detail.

 

1.  Let’s first take example 1 which is an ‘Interactive Mathematics Tutor’.

Partially Observable - In this case the agent is required to tutor the students who are using that computer based application on solving Mathematics problems. This agent can be implemented so that it gives a set of problems for the users to solve and then once the users input the answers it can compare them with the answer base the system has in its database and mark them as correct or incorrect and in the case of incorrect answers it can provide an explanation to why it was wrong. Further, it should have the capability of users inputting certain problems that they have with respect to Mathematics so that the agent can give advice on how to solve those. Therefore, we can see that based on the different user inputs and questions which cannot be predicted beforehand the environment is not fully observable but only partially observable.

Stochastic – Each input and response to the agent is not a continuous process where the next action is determined by the previous action. Each action such as providing advice to a question a user raised, grading a test done by a user, providing explanations to incorrect answers are not dependent on one another but are different detached actions. Thus it is a stochastic environment.

Episodic – The term ‘episodic’ refers to each agent action being belonging to a certain action rather than a continuous process. For example, for each question that the user asks the agent gives the answer or advice without depending on the previous tasks.

Static – In this case we can assume that the environment which the agent is operating in does not change while it is taking an action. For example, when the user has submitted the answers to the questions that the agent has given on Mathematics, then the agent would be correcting them and in the mean time, the user would not change the answers. Static environments are easy to implement.

Discrete – This agent is working on a finite number of distinct states such as answering questions, correcting answers, etc. It is not a continuous process which is like a time-critical application. Thus operates in a discrete environment.

Single agent – This Mathematics tutor is operating on its own and does not communicate with any other intelligent agents other than the users themselves who are humans. We can assume that this agent is operating in a single stand alone computer other than a networked system and that all the actions are performed on its own (single agent). There can be a variation to this agent where it is linked to a network of tutoring agents and each providing specific actions which would then yield a multi-agent environment which is beyond the scope in this case.

2.Now let’s consider the 2nd example which is a ‘Robot Soccer Player’.

Partially Observable – The robot soccer player can be implemented with certain specific actions such as kick, run, tackle, etc which are related to a soccer playing actions according to the percepts it receives. But we cannot predict for sure what the environment would be in advance because the each game of soccer would be different from each other based on the many different factors, some of which being the overall players’ playing strategies, players’ ability levels, ground status. Every soccer game is different and thus the environment can only be partially observable in this case.

Stochastic – The next state of the game is not completely determined by the current state and the action executed by the robot because there can be other factors such as movements in other players which makes the next state dependent on many factors yielding this to be a stochastic environment.

Sequential – The process of playing a soccer game is sequential since one action can lead to long term consequences. For example if the soccer playing robot scored a goal in the early stage of the game and if there were no scoring by the opponents then the soccer robot’s team would win the match showing how each action causes a sequential process.

Dynamic – The soccer playing environment is changing every moment. Based on each action of each player, positions of players, position of the ball, thinking and actions of other players at each moment, will change the environment in each single second, which can change dramatically while our robot soccer agent is taking a certain action. Thus it is a dynamic environment.

Continuous – The soccer game is a continuous process from start to the end of the game.

Multi agent – The robot soccer played would be playing with his fellow robot team members as well as with the opponents. This is indeed a multi agent environment where the robot soccer agent has to communicate with the fellow robots are also have the ability to recognize the opponent team’s robots and try to win the game for its own side.

 

3. The third example in the list was ‘Internet book shopping agent’. So let’s see how its environment behaves in detail.

Partially Observable – The internet book shopping agent would be a tool that the users can use in order to find the most affordable books on preference and ask it is order them on behalf of you to reach you by the required date of your liking. When we consider the agent it has to search through the online book sellers and other online merchant sites for the books, compare prices, check for shipping options and meet the budget given by the user in a nutshell. But there can be certain sites which do not let the autonomous bots (automated shopping agents) to order items from their sites by restricting access and also including many security options, also this agent does not have the ability to access the book selling that can go offline and also the agent can have missing and obsolete data derived from online sites. Thus, it is a partially observable environment.

Deterministic – The next state of the environment is purely determined by the previous state of the environment, because after comparing the prices and other factors of the respective book the agent would take the next action of ordering the book from the online site which optimizes the user’s requirements. Thus it can be seen that the next action is purely based on what it perceived in the previous states.

Sequential – The online shopping is done on a step-by-step process. Starting off with finding the book(s) with the correct specifications such as the author, name, edition, then it would compare the prices and other factors and then decide on ordering from the best site and then order the book(s). It can be clearly seen that this is a sequential environment.

Dynamic – It is also worthy of noticing that the prices of the books, the availability of the stocks, etc could change in each online book selling site, at the same time where the online shopping agent is taking the decision of from where to order based on the information gathered in the previous state. Thus, the online agent cannot just rely on the information it gathered at a past time, but has to check on each instance to check on changes occurring in the online sites with respective to the book or books of concern. Thus it is obvious that it is a dynamic environment.

Discrete – This is a discrete state environment with specific states starting from the user specifications for buying a book to ordering a book by the agent to meet the user’s requirements.

Multi agent – The online shopping agent might have to communicate with other online shopping agents which are roaming over the internet to gather information about the books and their features rather than visiting each online site on its own. This can lead to collaborative work which can be productive for all the shopping agents and lead to meeting the objectives faster than acting on its own. So, this can be multi-agent environment where there can be communications and collaborations taking place among the thousands of available internet shopping agents.

I think after the detailed explanation based on the above three examples and their respective environments, that our readers got a clear idea of how to determine an intelligent agent’s environment types. Now let’s move on to identifying what is an agent function and agent program.

 

Agent Functions&Agent Programs

An agent is completely specified by the ‘agent function’ which maps percept sequences that it receives through its sensors to actions. In AI, we have to know how to design an ‘agent program’ that eventually implements the above ‘agent function’. So in a nutshell, what the ‘agent program’ does is implementing a way of mapping each of the percept sequences that the agent receives from its sensors about the environment, to a action that the agent that t should perform ultimately to achieve its objective function.

Overall agent is a combination of the agent program and the agent architecture. For example, if the agent program implements an action called ‘move forward’, then the architecture needs to have certain mechanical objects such as legs, wheels or any motor which enables to move forward. In the case of our example of robot soccer player, for it to be able to kick and perform other actions required by a typical soccer player, the agent should have an architecture with robotic legs, arms, vision etc. The architecture can also be just a computer with keyboard input and screen if we are talking about the Mathematics tutor agent.

A typical agent program would take the percepts as inputs, append this to the percept sequences and look up the table which consists of percept sequence mapping to respective actions and output the action. Following is a high level pseudo-code which explains what a basic agent program should look like give that the percept sequence, action table is created in advance.

 

Practically, such program would not be implemented unless for very small and simple agents where the percept sequences are less and the environment is fully observable and static. Creating the entire look-up-table requires you to assume that the environment is static and fully observable.  Further, based on the number of percepts that the agent has and the number of possible percept sequences that it could get, the look-up-table size would grow drastically high causing it impossible to store and generating an impossible and tedious task to the designer of the agent. Practically since, most environments are not static, and fully observable as well as the designer of the agent would not know for sure prior to the implementation which percept sequence should cause which sequence, this approach is not feasible. Above is the simplest way of implementing an agent program which lacks sophistication.

 

Next in line

In general the main idea behind building intelligent agents is to meet a certain goal of each agent while makes it able for them to learn from the experiences while operating in their respective environment and apply those learning to get to the goal more effectively and efficiently. We would look at how AI goes on to achieve this task by looking at different types of agents and then how to convert them into learning agents. Following are types of agents which we can build to achieve certain tasks.

  • Simple reflex agents
  • Model-based reflex agents
  • Goal-based agents
  • Utility-based agents
  • Learning agents

 

We would look in to details of each agent type mentioned above and also about their differences in the next article. Await our discussion on more about intelligent agents, next month!!!

 

References

Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Norvig

Moving ahead with Intelligent Agents

Starting from today, the article series on Artificial Intelligence (AI) would be focusing on ‘Intelligent agents’ and search techniques which are two of the very useful and interesting sub areas in AI. Let us talk about intelligent agents, first. First of all, we should understand why agents are important in AI based systems. The term ‘agent’ is usually used to define a person which undertakes some tasks or actions in order to fulfill certain objectives. For example, in day to day life, a ‘real estate agent’ is a person who acts as an intermediary between sellers and buyers of real estate to perform the real estate based transactions. Further, you would have heard about ‘travel agent’ who takes care of the booking, handling and payment management of travelling with regard to passengers, who may be linked to a travel agency or may be working as a freelance agent. There are many more agents in real world who perform certain actions with respective their field of work to obtain certain objectives. All of these real world agents have paved way in defining an entity called ‘Intelligent agents’ in the subject of AI. With regard to AI, we are trying to build computer systems which can exhibit intelligent or rational behavior to perform certain tasks which as humans we need some assistance with. You can refer the first two articles on AI which discusses about the terms of rationality, intelligence and other basic terminology to refresh your memory, if required.

In AI, an ‘Intelligent agent’ is considered as an entity that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. With respect to a human being the sensors are eyes, ears and other sensory organs while the actuators can be considered as hands, legs, mouth and other body parts from which we perform a certain task. The environment is the situation or the area in which the agent acts. For example, the environment of a travel agent is the travel agency where information about travelling and information about passengers are available. Therefore, we can see that the function or the expectations from an AI based intelligent agent is closely related to what an agent does in the real world.

Intelligent Agents in detail

 

In more detailed terms, an ‘Agent’ is an entity which can perform the responsibilities and actions to achieve a certain goal acting upon the percepts received from the sensors about the environment, on behalf of another while learning from experiences with a less amount of human intervention

In AI there are certain terminologies one has to learn when dealing with agents which are described as below.

  • Environment – The environment in which the agent is operating in
  • Sensors – The ways in which the agent can grasp input and observe/feel the changes happening in the environment
  • Percepts – The input that an agent receives from its different sensors about the environment
  • Actuators – The medium in which the agent performs the required actions based on the given percepts. It can be a movement action where the actuators have to be wheels, legs (if it is a humanoid robot) or the actuators can be the voice where a robot or computer system provides feedback in voice enabled fashion.
  • Actions – The particular actions which the agent does in order to fulfill the given goal with the use of its actuators
  • Performance Measure – A measurement to find the successfulness of the agent’s actions based on how much it acts towards fulfilling the specified goal. In more scientific terms it is considered as an objective criterion for the success of an agent’s behavior. For example, for a computer based (AI-based) travel agent, the performance measure could be to maximize the profit generated from the sale of travel and booking while meeting the customer requirements up to a certain high level.

If we illustrate the basic functionalities and parts of an intelligent agent in a high-level picture, it would be as follows.

 

Figure 1 – An agent architecture – A high level view

 

Rational Agents

As we consider rationality (doing the right thing) is the most important aspect in terms of creating intelligence (refer AI articles 1&2 for more details on this), with respect to agents we consider building rational agents.

Generally, ‘Rational agents’ should strive to ‘do the right thing’ based on what it can perceive and the actions it can perform. The right action is the one that will cause the agent to be most successful. In more specific terms, for each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

Further point is that, agents can perform actions in order to modify future percepts so as to obtain useful information. For example, an agent can perform a certain intermediate action and get the feedback about that from the percepts and see whether it was a good action or not. So based on the percepts it received on that particular action the agent can decide whether it is a good action to perform in the future or not, in order to reach the specified goal. An agent is considered as ‘autonomous’ if its behavior is determined by its own experience. The way in which experience can help is that the agent would be able to learn and adapt based on the past experiences and act accordingly to future percepts.

PEAS structure

When designing agents in AI, we have to define a structure called ‘PEAS’ where each letter stands for a different concept linked to the design of the agent.

 

Figure 2 – PEAS definitions

If you are to design an agent then the first thing you should do is to define its PEAS structure. This would enable you to design the agent to meet its goal while it would make the implementation of the agent for focused. So, let’s look at some examples of how to define PEAS structure for different types on agents. After going through the following basic examples, you can also try out on defining some PEAS structures for agents for whom you think are essential in today’s world.

 

Example 1 – Interactive Mathematics tutor agent

  •  Performance measure: Maximize students’ scores on a specific test
  • Environment – Set of students, Mathematics exams
  • Actuators – Screen display showing the exercises, examples, corrections, scores, advice and tips; also the actuators can also include voice in the case that the agent is voice enabled so that it provides feedback to students via voice.
  • Sensors – Keyboard, voice(if the agent is going to be working on voice commands)

Example 2 – Robot Soccer Player

 

  • Performance Measure – No: of goals scored, No: of successful defends
  • Environment – Football ground, other players who are from your same team and also the opponents, spectators, referees, goalkeepers
  • Actuators – Arms and legs
  • Sensors – Visual Sensors, Auditory Sensors, Identification of colors and team player differences

 

Example 3 – Internet book shopping agent

 

  • Performance Measure – Ordering the required book(s) for minimum price, minimizing cost
  • Environment – Book selling web sites, other shopping agents, clients, financial institutions for payments
  • Actuators – Screen to Display ordered books, prices, place ordered, estimated time of delivery
  • Sensors – Keyboard input

 

Types of Environments

 

With relation to AI agents, we know that understanding the environment in which they operate in, is important when designing and building an agent. Based on the different types of environments, the percepts that the agent is going to receive would vary while the actions it should perform also depend on the environment of operation. Therefore, let’s identify the different environments in which an AI based agent can operate in.

Table 1 – Types of environments

 

The following section describes in detail what each of the above environment types mean

  • Fully observable – An agent’s sensors give it access to the complete state of the environment at each point in time
  • Partially Observable – An agent does not have access to the complete state of the environment through its sensors so has to act upon partial information
  • Deterministic – The next state of the environment is completely determined by the current state and the action executed by the agent
  • Stochastic – The next state of the environment is not determined by the current state and action of the agent so, it is completely detached
  •   Episodic – The agent’s experience is divided into atomic “episodes” (each episode consists of the agent perceiving and then performing a single action), and the choice of action in each episode depends only on the episode itself
  • Sequential – The choice of the next action depends on the previous actions
  • Static – The environment does not change while an agent is performing its task
  • Dynamic – The environment changes while the agent performs its tasks, so that the action may not result in the best action once the environment in changed
  • Discrete – A limited number of distinct clearly defined percepts and actions derived and returned to the environment
  • Continuous – There can be a continual flow of percepts via the sensors on which the agent has to act accordingly with a series of actions
  • Single agent – An agent operating by itself in an environment
  • Multi agent – Multiple agents operate in the same environment which may lead to inter-agent communication

 

The environment type largely determines the agent design because based on where it operates in the design of the sensors, actuators and also the percept receiving mechanism, action selection and successful operation varies. For example, an agent who operates in a fully observable environment, where it can observe all the changes occurring in the environment needs to have high number of very effective sensors to capture all those changes when compared to the partially observable environment where only one or two percepts would be required. Another example can be in a single agent environment, the agent only has to interact with the user where as in the multi-agent environment it should have the ability to communicate and exchange information with the other agents via more actuators and actions. Now let’s see in which types of such environments do the agents we described as examples in the previous section operate in.

 

Table 2 – Environment Types applicable to example agents

As an exercise, try to reason out why the different environment types were defined for the above 3 example agents. Think why one is a single agent environment while the other two are considered as multi agent environments. Likewise, try to convince yourselves the reasons about why those different environments are applicable to those agents. I would be giving an explanation on why it is so, in the next article so that you would have time to put on your thinking caps and think about it before I give you the reasons now itself.

 

Something to look forward to

 As I already mentioned, in the next article I would give reasons for selecting the specific environment types for the given agents. Then we would be moving on to understanding agent functions, the design agent programs and also about different types of agents. All these to come would be based on the details and terminology that was presented today about intelligent agent and their environments, so try to get a feeling about agents by reading this article. I hope you would be looking forward to read more about agents next time.

 

References

Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Norvig

Intelligent Agents

Starting from today, the article series on Artificial Intelligence (AI) would be focusing on ‘Intelligent agents’ and search techniques which are two of the very useful and interesting sub areas in AI. Let us talk about intelligent agents, first. First of all, we should understand why agents are important in AI based systems. The term ‘agent’ is usually used to define a person which undertakes some tasks or actions in order to fulfill certain objectives. For example, in day to day life, a ‘real estate agent’ is a person who acts as an intermediary between sellers and buyers of real estate to perform the real estate based transactions. Further, you would have heard about ‘travel agent’ who takes care of the booking, handling and payment management of travelling with regard to passengers, who may be linked to a travel agency or may be working as a freelance agent. There are many more agents in real world who perform certain actions with respective their field of work to obtain certain objectives. All of these real world agents have paved way in defining an entity called ‘Intelligent agents’ in the subject of AI. With regard to AI, we are trying to build computer systems which can exhibit intelligent or rational behavior to perform certain tasks which as humans we need some assistance with. You can refer the first two articles on AI which discusses about the terms of rationality, intelligence and other basic terminology to refresh your memory, if required.

In AI, an ‘Intelligent agent’ is considered as an entity that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. With respect to a human being the sensors are eyes, ears and other sensory organs while the actuators can be considered as hands, legs, mouth and other body parts from which we perform a certain task. The environment is the situation or the area in which the agent acts. For example, the environment of a travel agent is the travel agency where information about travelling and information about passengers are available. Therefore, we can see that the function or the expectations from an AI based intelligent agent is closely related to what an agent does in the real world.

Intelligent Agents in detail

 

In more detailed terms, an ‘Agent’ is an entity which can perform the responsibilities and actions to achieve a certain goal acting upon the percepts received from the sensors about the environment, on behalf of another while learning from experiences with a less amount of human intervention

In AI there are certain terminologies one has to learn when dealing with agents which are described as below.

  • Environment – The environment in which the agent is operating in
  • Sensors – The ways in which the agent can grasp input and observe/feel the changes happening in the environment
  • Percepts – The input that an agent receives from its different sensors about the environment
  • Actuators – The medium in which the agent performs the required actions based on the given percepts. It can be a movement action where the actuators have to be wheels, legs (if it is a humanoid robot) or the actuators can be the voice where a robot or computer system provides feedback in voice enabled fashion.
  • Actions – The particular actions which the agent does in order to fulfill the given goal with the use of its actuators
  • Performance Measure – A measurement to find the successfulness of the agent’s actions based on how much it acts towards fulfilling the specified goal. In more scientific terms it is considered as an objective criterion for the success of an agent’s behavior. For example, for a computer based (AI-based) travel agent, the performance measure could be to maximize the profit generated from the sale of travel and booking while meeting the customer requirements up to a certain high level.

If we illustrate the basic functionalities and parts of an intelligent agent in a high-level picture, it would be as follows.

 

Figure 1 – An agent architecture – A high level view

 

Rational Agents

As we consider rationality (doing the right thing) is the most important aspect in terms of creating intelligence (refer AI articles 1&2 for more details on this), with respect to agents we consider building rational agents.

Generally, ‘Rational agents’ should strive to ‘do the right thing’ based on what it can perceive and the actions it can perform. The right action is the one that will cause the agent to be most successful. In more specific terms, for each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

Further point is that, agents can perform actions in order to modify future percepts so as to obtain useful information. For example, an agent can perform a certain intermediate action and get the feedback about that from the percepts and see whether it was a good action or not. So based on the percepts it received on that particular action the agent can decide whether it is a good action to perform in the future or not, in order to reach the specified goal. An agent is considered as ‘autonomous’ if its behavior is determined by its own experience. The way in which experience can help is that the agent would be able to learn and adapt based on the past experiences and act accordingly to future percepts.

PEAS structure

When designing agents in AI, we have to define a structure called ‘PEAS’ where each letter stands for a different concept linked to the design of the agent.

 

Figure 2 – PEAS definitions

If you are to design an agent then the first thing you should do is to define its PEAS structure. This would enable you to design the agent to meet its goal while it would make the implementation of the agent for focused. So, let’s look at some examples of how to define PEAS structure for different types on agents. After going through the following basic examples, you can also try out on defining some PEAS structures for agents for whom you think are essential in today’s world.

 

Example 1 – Interactive Mathematics tutor agent

  •  Performance measure: Maximize students’ scores on a specific test
  • Environment – Set of students, Mathematics exams
  • Actuators – Screen display showing the exercises, examples, corrections, scores, advice and tips; also the actuators can also include voice in the case that the agent is voice enabled so that it provides feedback to students via voice.
  • Sensors – Keyboard, voice(if the agent is going to be working on voice commands)

Example 2 – Robot Soccer Player

 

  • Performance Measure – No: of goals scored, No: of successful defends
  • Environment – Football ground, other players who are from your same team and also the opponents, spectators, referees, goalkeepers
  • Actuators – Arms and legs
  • Sensors – Visual Sensors, Auditory Sensors, Identification of colors and team player differences

 

Example 3 – Internet book shopping agent

 

  • Performance Measure – Ordering the required book(s) for minimum price, minimizing cost
  • Environment – Book selling web sites, other shopping agents, clients, financial institutions for payments
  • Actuators – Screen to Display ordered books, prices, place ordered, estimated time of delivery
  • Sensors – Keyboard input

 

Types of Environments

 

With relation to AI agents, we know that understanding the environment in which they operate in, is important when designing and building an agent. Based on the different types of environments, the percepts that the agent is going to receive would vary while the actions it should perform also depend on the environment of operation. Therefore, let’s identify the different environments in which an AI based agent can operate in.

Table 1 – Types of environments

 

The following section describes in detail what each of the above environment types mean

  • Fully observable – An agent’s sensors give it access to the complete state of the environment at each point in time
  • Partially Observable – An agent does not have access to the complete state of the environment through its sensors so has to act upon partial information
  • Deterministic – The next state of the environment is completely determined by the current state and the action executed by the agent
  • Stochastic – The next state of the environment is not determined by the current state and action of the agent so, it is completely detached
  •   Episodic – The agent’s experience is divided into atomic “episodes” (each episode consists of the agent perceiving and then performing a single action), and the choice of action in each episode depends only on the episode itself
  • Sequential – The choice of the next action depends on the previous actions
  • Static – The environment does not change while an agent is performing its task
  • Dynamic – The environment changes while the agent performs its tasks, so that the action may not result in the best action once the environment in changed
  • Discrete – A limited number of distinct clearly defined percepts and actions derived and returned to the environment
  • Continuous – There can be a continual flow of percepts via the sensors on which the agent has to act accordingly with a series of actions
  • Single agent – An agent operating by itself in an environment
  • Multi agent – Multiple agents operate in the same environment which may lead to inter-agent communication

 

The environment type largely determines the agent design because based on where it operates in the design of the sensors, actuators and also the percept receiving mechanism, action selection and successful operation varies. For example, an agent who operates in a fully observable environment, where it can observe all the changes occurring in the environment needs to have high number of very effective sensors to capture all those changes when compared to the partially observable environment where only one or two percepts would be required. Another example can be in a single agent environment, the agent only has to interact with the user where as in the multi-agent environment it should have the ability to communicate and exchange information with the other agents via more actuators and actions. Now let’s see in which types of such environments do the agents we described as examples in the previous section operate in.

 

Table 2 – Environment Types applicable to example agents

As an exercise, try to reason out why the different environment types were defined for the above 3 example agents. Think why one is a single agent environment while the other two are considered as multi agent environments. Likewise, try to convince yourselves the reasons about why those different environments are applicable to those agents. I would be giving an explanation on why it is so, in the next article so that you would have time to put on your thinking caps and think about it before I give you the reasons now itself.

 

Something to look forward to

 As I already mentioned, in the next article I would give reasons for selecting the specific environment types for the given agents. Then we would be moving on to understanding agent functions, the design agent programs and also about different types of agents. All these to come would be based on the details and terminology that was presented today about intelligent agent and their environments, so try to get a feeling about agents by reading this article. I hope you would be looking forward to read more about agents next time.

 

References

Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Norvig

A quick recap

After a small break in the series of AI articles with no article appearing on diGIT magazine’s August issue, here we are again exploring the area of knowledge representation and reasoning with respect to AI. Hope our readers have not forgotten all the concepts which were introduced in the last couple of articles with respect to ‘First Order Logic’ which we are going to go in depth in today’s article. Just to give you a quick glimpse of what we presented in the last article (which appeared in diGIT’s July 2009 issue), I would remind you the concepts we discussed. We learnt what ‘First Order Logic’ (FOL) also known as ‘Predicate Logic’ is in the context of representing knowledge using logical symbols. We also learnt the syntax of FOL under two sections such as logical symbols and non-logical symbols. The descriptions on connectives, punctuation and variable fell in the logical symbol section while variables, predicate symbols and function symbols belonged to the non-logical symbol section. Then we also looked at the scope of the quantifiers such as ‘For all’  and ‘Exists’ , where understanding of the scope is highly essential to construct as well as interpret FOL based statements. Next we went to understand the semantics of FOL based statements and the article consisted of various examples to give the flavor of different interpretations of the statements. The last section also consisted of a comparison between FOL and Propositional Logic so that you could understand the pros and cons of each logical representation method. I hope you would go through the previous article and refresh your memory on the above stated concepts before going through today’s article so that you could get the most out of it easily.

Today we are going to look at interpretations, models, reasoning and resolution with regard to FOL which we would be discussing in the following sections in detail.

What is an ‘Interpretation’?

An interpretation is ‘an assignment to a variable which gives some semantic meaning to the predicate, function or statement in concern’. For example let’s consider a predicate as follows.

Boy(x)

Then all the possible assignments to the variable x in the predicateBoy() are interpretations.

Further, an interpretation assigns a denotation to all non-logical constants in the FOL language. It enables each term to be assigned to a specific object that it represents and based on that each sentence is assigned a truth value which gives semantic meaning to the FOL statements. Therefore, an interpretation is extremely important with respect to understanding and interpreting the meaning or the semantics of FOL. Interpretations in general specifies exactly which objects, relations and functions are referred to by the constant, predicate and function symbols respectively. Practically, when we are defining knowledge of a certain domain using FOL, we build up a specific set of available and useful interpretations which is known as ‘intended interpretation’ when we possess a certain understanding of the domain in concern. In such as case, for example if we are dealing with a domain of a school we know that certain constants such as ‘Bill’ are the intelligent boy where as ‘Jane’ is the smart girl. We may also know that the predicates ‘teaches’ refers to the teaching relationship between subject and teacher while ‘study’ refers to studying relationship between student and subject.

 

‘Model’&‘Tautology’ – An overview

If an interpretation satisfies or makes a certain FOL statement true (valid) in the domain of concern, such interpretation is called a ‘Model’ of that domain.

You may also see that a certain interpretation can make the FOL statement be invalid or leading for its semantic meaning to be false. So in that case it is not a model of that domain. Let’s try to illustrate this concept with a simple example in FOL.

 

In the above case the domain in concern is restricted to the specific constants defined which are as follows.

  •  Bob
  • Jack

So if we assign each of the above constants which could be interpretations in the FOL statement number 4 it would result as follows.

Interpretation 1:- x=bob, y=bob

This result is false and is not valid since there is no atomic statement which says that OlderThan(bill, bill) is true. We only consider the given atomic statements as true and all the others as false when dealing with knowledgebase systems. Therefore conjunction of two true statements and one false statement leads to a false conclusion. Let’s try the next interpretation.

Interpretation 2:- x=jack, y= bob

This result is also false and is not valid since there is no atomic statement which says that OlderThan(jack, bob) is true. We only consider the given atomic statements as true and all the others as false when dealing with knowledgebase systems. Therefore conjunction of two true statements and one false statement leads to a false conclusion. Let’s try the next interpretation.

Interpretation 3:- x=bob, y= jack

This result is true because the atomic sentences Boy(bob),Boy(jack) and  OlderThan(bob, jack)are all true and defined in the domain. So the conjunction of all three true values lead to the statement ElderBrother(bob, jack) being interpreted as true. Therefore the interpretation, x=bob, y= jack is a ‘model’ for this example.

If a FOL statement is resulted as valid or gives value true under all possible interpretations applicable in that domain, then such FOL statement it is called a ‘Tautology’. So in such a case under all possible interpretations the truth value of the statement becomes true thus showing it is valid under all conditions pertaining in that domain, which shows that it is a ground truth.

 

Resolution based reasoning

This topic is the ultimate objective of learning all about FOL. After constructing a knowledgebase using FOL statements adhering to the required syntax and semantics taught before, the objective is to raise queries to the knowledgebase and get some answers or reasoning to arrive at certain conclusions with regard to the domain in concern.

Resolution is a form of ‘rule of inference’ which define the statements of what formulas could be inferred from a set of other formulas. In other terms, the formulas or statements that we raise as queries to the knowledgebase should be inferred using the formulas or statements belonging to (residing in) the knowledgebase as a rule of inference. Such process is called ‘Resolution’. For one to go ahead with this reasoning process, it is first required to pre-process the statements appearing in the knowledgebase and convert them to a form known as Conjunctive Normal Form also known as CNF for short. CNF converts each statement to be a ‘conjunction of disjunction of literals’. Every propositional formula can be converted into an equivalent formula in CNF based on rules about logical equivalences such as the double negation law , the De Morgan’s law and the distributive laws of logic which are shown in detail as follows.

 

We have looked at converting propositional logic statements to CNF form and performing resolution on propositional logic based systems in the previous article published in May 2009 issue of diGIT. You can have a look at it to refresh your memory again since it is somewhat similar to the resolution used here in FOL, only difference being we are now dealing with predicates and functions in contrast to simple propositions in propositional logic.

Following are the steps of converting a FOL based statement/formula to CNF form.

  1. Eliminate implication by replacing it with negation and disjunction.Example:- P(x) à Q(y) ≡ ~P(x) V Q(y)
  2. Move negation inwards so that it appears only in front of an atomic sentence.

    Example:- ~(P(x) V Q(x)) ≡ ~P(x) ^ ~Q(x)

    Also when quantifiers are present follow the following rules when moving negation inwards.

  3. Standardize variables – This ensures that each quantifier is over a distinct variable by renaming the variables as required. For sentences which has the same variable name appearing twice or multiple times, change the name of such variables to be unique in order to avoid confusions later.

    4.     Skolemization – Eliminate all remaining existential quantifiers Process:- For variables within existential quantifiers rename each variable with a                      distinct constant.

                       
5.     Move universal quantifiers outside the scope of conjunction and disjunction and drop the universal quantifiers – At this point, all                          remaining variables must be universally quantified and the sentence is equivalent to one which all the universal quantifiers are moved to             the     utmost left. Therefore, we can drop the universal quantifiers now.
6.      Distribute conjunction over disjunction

Process:- Which requires De Morgan’s law and/or distributive law stated above.

Example:- P(x) V (Q(x) ^ R(x)) ≡ (P(x) V Q(x)) ^ (P(x) V R(x))

7.    Write resulting statement which is now in CNF form which is logically equivalent to the original statement.

After converting the statements in FOL which were residing in the knowledgebase in to CNF form following the above stated steps, we have to now consider how to use that to come up with resolution. If we are given a query or another statement to check the answer or check whether it is consistent with the knowledgebase respectively, we have to use the resolution as follows.

First we have to take the negation of the query to be answered or the statement to be checked for consistency.

“Why do we take the negation of this?” may be a question that might be lingering in your mind now. Let’s see the why it is required. Resolution proof is a method which is ‘refutation complete’. This means by taking the negation of the statement to be proved or answered we show that using that and the converted knowledgebase statements into CNF when unified would result in a null value (refutation) if the statement is true or false otherwise. This is a very simple concept. Consider that we have to prove that ‘A’ is true. We know certain facts related to ‘A’. If we show that using the related facts and the negation of ‘A’ leads to a refutation or a null statement we can show that ‘A’ is indeed true. This is somewhat similar to the ‘proof by contradiction’ approach used on logical and mathematical theorem proving which some of you may have heard when doing Mathematical subjects in school.

Now let’s go through a simple example where reasoning is done through resolution method mentioned above.

 

Example 1:-

Now let’s follow the unification procedure of resolution.

  • Write each statement separated by the conjunctions in the resulting CNF form separately. Also write the negated to be proven statement alongside of them.
  • Then check whether we can unify a pair of statements by assigning a value for each variable inside the predicate symbols if required. Unification works such that if you find the negation and non-negated form of the same predicate/function with the same variable value you can cancel them out and write the rest of the statement. This is because the conjunction of negated and non-negated statement which is similar yield to null. For example you can see A ^ ~A = Null. Therefore, if we have predicates initialized with the same variable as P(a) ^ ~P(a) then it results in null and can be cancelled off.

Therefore, it is a contradiction (refutation).

Therefore, we can show that if we did not take the negation of Q(a) it would have been proven by the available statement in the knowledgebase. Thus we can conclude using resolution by refutation that; “Q(a) is inferred by (x) P(x) ^  (P(a) à Q(a))”.

 

Example 2:-

Let’s consider another small example with respect to placement of boxes.

On(x,y) – Predicate to show that box ‘x’ is on box ‘y’

Red(x) – Predicate to show that the color of box ‘x’ is red

The known facts which are in the knowledgebase are as follows.

 

All of the above statements are atomic sentences which are already in CNF form so no need of conversion.

We have to show that:-

There exists a box which is red in color and on top of that lies a box which is not red in color. This statement can be written in FOL as follows<

So to use with resolution method let’s take the negation of the above statement and unify with the known facts from the knowledgebase and see whether it results in a refutation.

Take Negation and follow steps of converting to CNF as follows.< Now let’s do the resolution process as illustrated as below.

So this ultimately leads to a refutation showing that the statement:-

is valid in terms of the given domain using resolution proof.

 

Next in row

Today we had a long discussion about interpretations, models and reasoning and resolution with regards to FOL. Hope you got a good idea about this process. Try out some practical examples you come across to practice these methods. You can first represent them in FOL statements and then try to reason with resolution after converting to CNF as we discussed today.

I hope you got a basic idea about Knowledge representation and reasoning with relevance to Propositional logic and FOL during these series of articles. Although there are many more areas to discuss in the sub topic such as other logic representations, Ontology modeling, semantic web, etc, I think we should move on to other sub areas of AI now since, the aim is to get you all familiarize with many sub areas so that you can get a good understanding of AI as a whole. Later in life you can study in depth in to each area so that you would be able to master it. Therefore, I would move on to talking about intelligent agents and search techniques which are widely used in AI applications in the next batch of AI articles to follow. Hope you got a fairly good understanding of the Knowledge representation and reasoning techniques we discussed and enjoyed the articles on AI so far and hope you would look forward to the next batch of articles in a new sub area of AI.

 

References

Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Norvig

Knowledge Representation & Reasoning – Ronald Brachman & Hector Levesque

This would be the fifth article on AI to be presented to the readers in diGIT. Just to recap what we had looked at throughout this series of articles; we first introduced you to the history and the field of AI at a glance, then we moved on to identify the basic concepts of AI and next we moved on to the area of Knowledge representation and reasoning which is one of the key areas in AI. We are still in the process of explaining about various methods and ways of knowledge representation and reasoning. In the previous article we focused on how to represent some more general statements in propositional logic, reasoning methods and the advantages and disadvantages of using propositional logic. Now let’s move forward and look at a more expressive language which is widely used for knowledge representation and reasoning in AI. It is none other than ‘Predicate Logic’ which is also known as ‘First order Logic’. Throughout this article we would be looking in to the basics of Predicate logic and how to represent simple knowledge in a knowledgebase using this method.

 

‘Predicate Logic’ also known as ‘First Order Logic’

First order logic (which would be referred to as ‘FOL’ in the rest of the article) is another way of expressing and representing knowledge apart from the propositional logic which we learnt in the previous articles. FOL has some additions to the propositional way of knowledge representation with the inclusion of predicated and quantifiers which have more representation power when compared to just propositions, which we are looking at now.

First as we have to look at the syntax of FOL. Syntax means the groups of symbols are other things when arranged in a certain way give properly formed sentences. It is extremely essential to know the syntax of a logical language in order to use it correctly and effectively in knowledge representation and reasoning.

Syntax of FOL  

FOL has two types of symbols used which are known as logical symbols and non-logical symbols. First let’s take a look at the details about the above two types of symbols used.

There are three sorts of logical symbols used in FOL which are explained as follows.

Punctuation – Just as in English language we have the punctuation symbols to express the meaning of the sentence in a proper manner. The main punctuation symbols used in FOL are comma, period, and brackets (“,”, “.”,”()”)

Connectives – These help to connect two or more predicates together to form a meaningful sentence that is expressed in FOL. There are general binary connectives such as negation (~), conjunction (^), disjunction (V), implication (->), bi-conditional (<->) while in addition to them there are some new connectives known as quantifiers which are used to express the meanings such as ‘There exists’ , ‘For all’  and ‘logical equality’ (=). These quantifiers were lacking in the propositional logic we learnt before so the knowledge expressive power was limited. But here with the existence of quantifiers more useful facts can be expressed about the domain in concern

Variables – These are used to specify the symbols that can be used for the predicate which are usually named as a,b,c,…or x,y,z,….The convention is to write variable in lower case letters.

Then the non-logical symbols which are applicable and defined based on the domain in which it is being used for are discussed as follows. The naming as well as the usage of such depends on the application or the domain in concern unlike the logical symbols which are like the ground terms for FOL

Predicate symbols– As the name implies the other term, ‘Predicate Logic’ is used for FOL due to the fact that it uses predicate symbols. These can be defined as any way as we like based on the domain in concern having variables describing what each predicate is linked/referred to. These merely show the relationship between variables based on the predicate they are attached to. Each predicate symbols has an ‘arity’ (arity >=0) which defines the number of arguments it takes. Usual convention is to start predicate symbols names with upper case letters and no spaces are kept to separate words but each new word is started with an upper case letter. Following are some examples of predicate symbols.

§  OlderThan(a,b) – This means ‘a’ is older than ‘b’. Here the predicate is the terms ‘OlderThan’ with two variables linked to it as ‘a’ and ‘b’. Therefore we can say that this predicate has two arguments thus its arity is two.

Female(a) – This specifies a predicate which defines the term ‘Female’ and shows that variable ‘a’ is a female. The arity of this predicate is one

  • Function symbols – In addition to just predicates, FOL has the capability of expressing functions. These also has the same features as predicates like consisting of number of arguments. Usually the functions names are started with a lowercase letter but the each new work is started with an upper case letter. Following are some examples of function symbols

    § bestFriend(c,a) – Which defines the function that ‘c’ is the best friend of ‘a’
    §  fatherOf(c,b) – This tells that ‘c’ is the father of ‘b’.

 

Scope of quantifiers

Further we need to have a look at the scope of quantifiers that we described in the logical symbol section.

Generally when the quantifier ‘for all’ > is used, it means for all the variables defined under that should be true. For example if we say:-

  OlderThan(x,y)This means for all the variables in x and all the variables in y, always x is older than y. Therefore, the scope of the quantifiers are there for the entire predicate OlderThan(..,..). Further, this can also be written as x,y. OlderThan(x,y) – where the ‘for all’ quantifier is applicable to both variables x and y so there are specified as separated by commas instead of indicating two quantifier symbols, which gives the same meaning as above.

If we have a sentence like below, the identification of scope of the quantifiers become more complex.

 

In the above FOL statement, the predicates appear as general terms without specific names as ‘P’ and ‘Q’. The occurrence of variable ‘x’ in both locations are bound by the ‘for all’ quantifier appearing at the start while the scope of the ‘y’ variable is bound by the existential quantifier at the middle. There is no free variable here in this sentence because both the variables x and y are bound by the scope of the two quantifiers, If we have a look at the following slightly different example, we would be able to see that the there is a free variable which is not bound by any quantifier. When there is a free variable, we can assign that variable with any value we like since it is not bound by the scope of the quantifiers in use. This is useful in the reasoning of the knowledgebase with different reasoning methods which we would look at later in the articles to follow during the next months.

x. Q(y) ^ $y(P(x) V Q(y)) – Here you can see that the variable ‘y’ appearing for predicate Q at the start is not bound by any quantifier because it is out of the scope of such and thus ne considered as a ‘free variable’.

 

Semantics of FOL

As we already know from the previous article about propositional logic, what ‘Semantics’ mean of a language, let’s quickly recap what it is again. Semantics describe the meaning of the sentences. After we express knowledge in based on the syntax of the language, the sentences that we constructed have to be meaningful in terms of providing useful information. The semantics describe such meaning of those expressions.

Based on the logical and non logical symbols which are shown in the FOL statement, we arrive at its meaning. Since the non logical symbols are application/domain dependent we cannot specifically arrive at hard and fast rules for the meanings across all domain. Instead, what we do it based on the non-logical symbols such as predicates and function symbols introduced for a certain domain, we arrive at meaning for those FOL statements which only apply to that domain.

For example the following FOL statements mean in terms of explaining family relationships:-

brotherOf (tom, jane) – Tom is the brother of Jane

Female(jane) – means Jane is a female

Male(tom) – Tom is a male

x. Boy(x) à Person(x) ^ Male(x) – This means for all the constants which can be substituted for variable ‘x’ a boy is a person who is a male.

Now based on the above syntax and semantics if the language we can represent the knowledge according to FOL. Further how do we know what is true and what is false. Every sentence that is expressed as a FOL statement in the knowledgebase is considered as true. Al so remember that, all the things which are not expressed and defined in the knowledgebase are considered false when we are trying to reason using this knowledge. For example, assume that we have been given the following knowledgebase describing about some sports preferences of some students which is represented in FOL.

 

 

From the above we can conclude based on the semantics, that the following are true.

Peter is a boy

Susan is not a boy

Peter plays Soccer

Susan plays Tennis

All the other things (although we know by common sense can be true) which are shown as below are considered false, because they have not been explicitly defined in the knowledgebase. The knowledgebase only knows the facts that we have clearly expressed in terms of the FOL statements and hence anything else is considered as false.

Susan is a girl

Peter also plays tennis

Let’s also look at constructing more complex sentences with the use of FOL for a domain considered as a school

“All the students in school ‘ABC’ are boys” (‘ABC’ is a boys’ school)

    •  x. StudentOf(‘ABC’,x) -> Boy(x)

      § This shows that using the predicate ‘StudentOf’ we are specifying the relationship between the school and the students and the first argument given as ‘ABC’ shows that we are talking about students of school specifically named as ‘ABC’.

      Or without going in to details we can specify it simply with a single predicate as BoysSchool(‘ABC’). But the problem here is there is no mentioning about the characteristics/definitions about the students of the school which we might need in the other statements about the school.

    • “Some students of ‘ABC’ who are good in studies(intelligent) are also good in sporty

      y. StudentOf(‘ABC’,y) ^ Intelligent(y) -> Sporty(y)

      See the difference here. Since only some of the students are good in both studies and sports we use the quantifier ‘There exists some’

Likewise, you can define any domain you like and try to express those in FOL using the logical and non logical symbols explained in this article as way of practicing and getting used to these syntax and semantics.

 

FOL vs. Propositional Logic

Now let’s have glance as to what are the main differences between Propositional Logic which we learnt in the previous two articles and FOL which we learnt today. It can be seen that the FOL is way better than propositional logic to express complex domains in a much easier and effective way. This is made possible with the introduction of predicates and function symbols which can have any number of arguments as required depending on the domain/application and also with the availability of quantifiers and other added logical symbols. The following table provides a descriptive explanation of the differences between these two methods of knowledge representation we have learnt so far.

 

 

 

Something to look forward to

Today, we looked at FOL and its basics with respect to introduction, syntax, semantics, scope of quantifiers, representing statements in FOL and comparison with propositional logic. These provide the building blocks of understanding how to express knowledge with the using FOL, which is extremely important to know and master as a person interested in AI, because the concepts of FOL and knowledge representation is widely used across domains in real world applications as well as in theory which is vital to understand more complex reasoning and representation methods. Next time, we would be going in to more advanced topics in FOL such as interpretations, reasoning and resolution which are significant concepts and processes that one must understand with respect to the area of knowledge representation and reasoning.

 

References
 

Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Noving
>Knowledge Representation&Reasoning – Ronald Brachman&Hector Levesque

Recap and what’s next?

In the previous article we looked at the what ‘Knowledge Representation and Reasoning’ is all about and how it is linked to Artificial Intelligence and also went on to look at the basics of the most simple knowledge representation method with the use of propositional logic. We learnt the syntax and semantics of propositional logic and how to represent general statement in accordance. Today, we would focus on how to represent some more general statements in propositional logic which would ultimately build the knowledge base while looking at some reasoning methods and the advantages and disadvantages of using propositional logic in this context.

 

Representing a problem in propositional logic

Let’s take a simple domain and try to represent the facts and knowledge about that domain using the basics of propositional logic that we have learnt so far.

Domain/Problem in concern:- There is 3X3 grid structure (composed of 9 squares) where a robot has to traverse from one square to the other starting from his initial location to get to the location where a secret box is kept. There is a hole in one square location for which if the robot went in to it, it would fall and break. The robot has to avoid that square. The requirement is that the robot has to safely traverse this grid and get to the location of the box which in which he can find some gold. Another condition is that the robot can only move left, right, up and down (it cannot traverse in the diagonal direction). When it reaches a square with the location of the hole adjacent to it, it would give an alarm.

Let’s represent the domain with an illustration as follows.

 

 

 

 

For ease of demonstration I have named the squares in the grid according to the row number and column number as (1,1), (1,2), (1,3) etc.

Now let’s try to represent this simple domain in propositional logic. Let’s define the following propositional symbols required.

H(x,y) – represents that there is a hole in the square represented by (x,y)

G(x,y) – represents that the secret box with gold in located at square (x,y)

A(x,y) – represents that the alarm to notify that one of the adjacent squares has a hole in it when the robot reaches (x,y)

R(x,y) – represent where robot is located

Propositional logic rules constructed out of the above symbols are as follows.

Rule 1(About where the hole is)  :-     H(2,2)

Rule 2(Where the secret box with gold is):- G(3,3)

Under what conditions the alarm would be sounded which has to be written for all the squares, but here only written for some squares for simplicity ( Alarm would be sounded if and only if there is a hole in one of the adjacent squares)

 

Rule 6(Where the robot is initially) :- R(1,1)

Rule 7(Possible moves for robot from initial position to a square where there is no hole):- These also have to be defined for each square for the robot movement and here only 2 such statements are shown for simplicity.

 

Once all such statements are defined we can insert those in to the knowledge base. All the rules we have come up with are true (saying that based on the domain in consideration, the truth value for each of the rules are true) Therefore, if we combine them with conjunction connective (˄) , then the entire long statement should be true as well, based on the truth values and semantics of the conjunction connective which we discussed last time.

Now let’s move on to see what logical inference is and how it would be used.

 

Logical inference

The term ‘inference’ is defined as an ‘act or process of deriving a logical consequence conclusion from premises’ as per Wikipedia. This simply means, based on the facts that we know about the domain in concern (such as the rules we defined above for the robot’s example) how do we arrive at a conclusion (like whether it is good for the robot to move to square(2,2), etc).

Inference is related with the notion of ‘entailment’ which I would try to describe as simply as possible. If there are two sentences A and B A is logically entailed by B is denoted as

A |= B

This means that the sentence A is logically followed by sentence B. If we try to define it more formally, the term entailment stands for A|= B, if and only if every model or assignment which makes A true makes B also true.

 

Reasoning with Propositional Logic

In order to come up with conclusions based on the defined facts about the domain in a knowledge base we should know the different methods in which we can derive such conclusions or inference. Following are some methods which can be used for reasoning.

 

1. Inference Rules

a. Modes Ponens rule:- This says if we are given that A -> B (A implies B) is true and also that A is true, then we can conclude that B is also true. We can show by the definition of implication based on truth tables that this rule is valid such that if A˄ (A->B) is true then B should also be true.

 

b.    AND elimination rule:- If we have a statement as A˄B is true, then we know by the semantics of AND- connective that for this to be true it is necessary for both A as well as B to be true individually. Therefore, when given that A˄B is true, we can either infer A or infer B.

 

c. Using Resolution:- This is a technique is very common in use for coming up with inference in most of the logics not only with propositional logic. For this to be applied we have to first convert the statements we have defined for the knowledge base in to a form known as “Conjunctive Normal Form” or CNF for short. This means nothing but, all the statements have to be converted so that the statements appear as a “conjunction of disjunctions of literals” as in the form below.

(A˅B˅C) ˄ (D˅E˅F) ˄ (G˅H) ˄ ………………..

In this case all the other connectives such as implication, bi-conditional has to be replaced with respective conjunctions and disjunctions and there are some specific steps to follow in order to convert a general statement in propositional logic into CNF form. Following are the steps required to be followed in order to convert a general statement in to CNF form. The steps have to be considered in the given order.


Once we have followed the above steps and convert propositional logic statements in the knowledge base in to CNF, we can use the resolution algorithm to come up with conclusions. The details about resolution algorithm is too complicated to be shown in a article like this which only focuses on giving the basics of the topic, so I would leave it out for now and introduce the resolution algorithm in the later articles where it would come in again when we move on to predicate logic and other reasoning methods.

 

Advantages and Disadvantages of Propositional Logic

Now let’s have a quick look at what are the plus points for using propositional logic in knowledge representation as well as identify why it is not the best method to do so.

Some of the advantages of using propositional logic are as follows.

· Simplest logic

·  Limited number of connectives and less syntax

· Easy to construct the knowledge base

Despite the above good points about propositional logic, it is not one of the most commonly used logical representations in knowledge based systems used in practice other than for small examples, small problems for understanding purposes because of the following limitations.

· Have to define a propositional symbol for each of the facts you want to represent about the domain. If there are so many facts you have to define in the given domain, this would not be practically efficient

· Very primitive and is difficult to define relationships between the objects in the domain

· The definitions such as for all, for some kind of quantifiers are not available therefore, we have to explicitly define rules for each and every condition which is a tedious task

 

Coming up

In this article we emphasized on the usage of propositional logic as a knowledge representation language while looking at how to reason with it, methods used in such case and also advantages and disadvantages of using this type of logic. In the next article, we would be moving to a more complex more useful and practically used type of logic known as ‘Predicate logic’ or ‘First order Logic’. We would try to understand the similarities or differences between these two logics and also get an idea about the basics of predicate logic in the next article.