Problem Solving through Searching
01/24/2010 11:22 pm By Chathra Hendahewa | Articles: 11
The first article on this year’s Artificial Intelligence (AI) series would be dedicated to introduce our readers about the importance and requirement of searching in problem solving. If you can recall from the last year’s article series we learnt the basic foundations of AI, Knowledge representation and reasoning and about intelligent agents. One main area of AI which we didn’t yet look at is how an intelligent agent achieves its goals given a lot of different possibilities. Therefore, in today’s article you would be able to understand how the problems are tackled by intelligent agents or any other software program in determining which method or option is better over the other available options in fulfilling their tasks.
Steps in Problem SolvingThere are number of steps involved in problem solving. As you may remember from the previous articles on intelligent agents, the agents are required to maximize their performance measure defined based on the task or tasks they have been assigned to do. Further, each agent has to try their best to achieve the goal defined while maximizing their performance measure which in turn requires it to find the best option out of the available alternatives. So this process of problem solving is explained in detail as follows.
- Goal Formulation – Defining goals help in directing the behavior of the agents towards that specific goal or goals rather than deviating from them. Formulating a goal based on the agent’s performance measure ensures that the agent has clear understanding of its objectives. Even in day to day life, if we have a problem at hand, first we define a goal/objective which would in turn solve the problem and work towards achieving it. This is the best way to get a good solution for the problem rather than being going all over the place and wasting time and other resources to solve a problem. This is the first step in problem solving.
-
Problem formulation - This is the process of deciding which actions or states to be considered to achieve the goal defined. Therefore, given a particular state in the environment and having various alternative options available in order to get to the goal state, the agent has to select the most beneficial option (in order to meet its goal while being achieving its performance measure). Such process of selecting the best possible sequence of actions from the available options is called ‘Searching’ which is of great importance to the area of problem solving.
- Search – Finding the best possible sequence of actions to lead to the goal out of all the available actions
- Solution – Once such best sequence of actions is chosen it is called the solution. In Computer Science sense, one has to implement a search algorithm which would take the defined problem and the available options as the input and outputs the best possible solution.
- Execution – Once the solution is given from the search algorithm, the agent has to execute the proposed set of actions in order to meet the goal.
Defining Problems & Solutions
There are important terms used in AI literature when defining a problem and its solutions, which would be defined in the following section.
A problem has to be defined by four main components.
- Initial state – This is the state which the agent starts at. This is important because for the problem to be addressed, one should first know where or what the agent is doing at the start so it can then determine what it needs to do next in order to reach the goal in the end.
- Successor function – This provides a description about the possible actions available to the agent given a particular state. For example, if you are in state ‘s0’ and this should define is pairs with first argument being which actions are available for the agent to perform and the second argument being what is the next/successive state it moves to after taking each possible action.
Combining the above two terms, another two useful terms can be defined. Those are the state space and the path which are explained as follows. The combination of initial state and the successor function defines the state space of the problem that the agent is faced with. This implies that the definition state space is the set of all possible states reachable from the initial state, given the agent’s set of possible actions. The state space can be represented as a graph where the states are shown in nodes and the arcs between the nodes depicting the actions that take the state from one node to the other. A path in the state space is a sequence of states connected by sequence of actions. In graph notation, it is the nodes and the arcs which define the path from one node to another node.
- Goal Test – This is the testing of whether a particular state is the goal state or not. At each state in the state space the agent has to check whether it is the goal state or not, because if it is not the goal state, then it has to search for more paths to reach the goal and if it is the goal state, then it has to stop the search. This can be achieved by defining an explicit set of states out of the state space which can be goal states and only check those states or defining the goal state as an abstract property of the goal state.
- Path Cost – This is the function that assigns a numeric cost value to each of the paths available. The cost function has to be defined based on the agent’s performance measure. For example, if the agent’s performance measure is to reach the goal in less number of steps then the path cost function should assign value 1 to each arc in the state space graph from one node to the other. In contrast, if the performance measure is to reach the goal in less time (given the assumption that the agent traverses the graph in the same speed throughout), the path cost function should assign the actual distance between two nodes along each arc or the time it reaches to go from one node to the other.
A solution to a problem defined by the combination of the above four parameters, which is the path that takes the agent from the initial state to the goal state while achieving the optimal path cost.
Understanding real world problem formulationSome real world problems that could be formulated as explained above in order to find solutions via searching are discussed below. Try to think of some more real world problems you have heard about or come across in life and how the above method of problem formulations and solving via searching can be applicable to them.
- Route-finding problems – This is a very common problem which is found across different domains such as travelling form one city to the other, routing in computer networks, air line travel planning, etc. For example, the general flavor of this problem is that you are at an initial place and you would like to travel to another place given certain constraints such as lowest time, lowest disturbances, etc. In order to do this we can formulate the problem with the problem formulation method introduced before by defining the initial state, state space and successor function, goal test and path cost.
For example if you want to travel from Colombo’s Bandaranaike International airport to Tokyo Narita airport, the problem formulation would be as follows.
- Initial State – Bandaranaike International Airport, Colombo, Sri Lanka and the current time
- Successor function – Any flight scheduled to leave the airport in Colombo after the current time plus the airport-transit time headed to Tokyo Narita airport.
- Goal test – There might be stop overs from the flight in between Colombo to Narita at may be Singapore, Malaysia. So the goal test should determine out of the stops of the air plane what is the goal state; which is Tokyo Narita airport.
- Path cost – This depends on the cost that the passenger is willing to incur, His/her preferences with regard to low travel time, non-stop flights, waiting time, airplane carrier, seat availability, etc.
- Touring Problems – One may view this as quite similar to Route finding problems but there is a unique distinction among these two. The state space needs to have not only the current location but also the set of states already being visited unlike in route finding problems. Each intermediate state should know where it is now and also where it has been to before.
- TSP or widely known as ‘Travelling Salesman problem belongs’ to the family of touring problems and requires that each city in the state space to be visit once. Further the goal is to find the shortest tour which would take one from one city to the goal city such that each city in the state space is visited only once.
- Robot Navigation – In building robots to move from one place to another to perform a certain task it is important to define the initial state of the robot in terms of coordinate locations, surface, orientation (such as facing south, north, east or west), position (whether it is currently standing, sitting, etc) and then based on the robot’s possible actions define the successor functions. The formulation of the problem in terms of defining the goal and the path cost should be in line with the robot’s defined goal and performance measure. It is also worthy of noting that with the increase of possible actions of the robot, the state space becomes very large making it a hard search problem where scientists and researchers are trying to come up with fast and improved algorithms. Further, since a robot has limited sensing capabilities via in built cameras and other sensors, there could be mishaps in the percepts they receive about the current state and successor functions and there could be certain errors too. Therefore, robot navigation is a very challenging problem to address with higher precision.
- Internet Search – The World Wide Web can also be viewed as a graph with interconnected nodes and arcs which is what we are referring to as the state space in the problem formulation. Searching answers for questions, for information can also be defined as a problem where the huge internet graph has to be traversed in order to find the best possible answers to queries and other information. Companies like Google, Microsoft, Ask.com who are pioneers in building the internet search engines also has incorporated the methods defined by such search techniques, that we would are discussing throughout. It is also worthy to note that internet search techniques are an vast field of research entirely by itself now, because of the wide use of internet based search and such applications, which is beyond the discussion of this article series.
More to look forward to
Today we looked at a new topic in the AI series, as what are the basics of problem formulation and searching. This is an area which is useful all throughout the field of AI, because the essence of AI is to make machines find solutions to problems in an efficient manner. This involves a lot of searching techniques ranging from the basic methods to complex optimized search mechanisms. In the next month’s article, we would look at some more definitions of searching and then would move on to understanding what uninformed and informed search is all about.
References
Artificial Intelligence – A modern Approach, Second edition, Stuart Russell & Peter Norvig
Post new comment