Chapter 3 - Solving problems by searching Flashcards
Define a search
A search is the process of computing/finding the path that leads from your current state to the goal state.
Define problem solving agents
Problem solving agents use atomic representations, states of the world that are considered as wholes. This means that they do not keep an internal structure at all. Very simple units.
I suppose this means that the agents following this scheme has no internal state in the sense that they only find a solution path of actions to perform. This doesn’t require monitoring of states. Since we assume that the task environment is known, fully observable and all that, it is reasonable to think that an agent can find a solution and shut its sensors off afterwards. In other words, there is no more interaction between the agent and other agents/objects in the TE after the route has been found.
Define planning agents
Planning agents are goal based agents that keep an internal state of some type, factored or structured representations of states.
I believe this means that planning agents are always monitoring their percepts, because their actions rely on interaction. Problem solving agents, on the other hand, use a current state and knowledge to find a solution. When a solution is found, the sensors can shut down, and the agent can execute the path that it has constructed. This means that the actions are actions that is to be performed regardless of anything else.
Now, keep in mind that we consider the following task environment: episodic, single agent, fully observable, deterministic, static, discrete and known. You cannot get it simpler than this.
What do we mean by “informed” algorithms?
Informed refer to knowing how far it is to the goal
What do we mean by “uninformed” algorithms?
Uninformed algorithms dont have a clue on where a goal might be. Therefore their only solution is to systematically explore the graph.
When we say, in this chapter, that we discuss environments that are known, what do we mean?
Name an example
A known task environment has a complete transition model. It knows everything about actions and what they do.
That we know the outcomes of our actions.
We refer to task environments that we “know”. This means that if we were to choose a road to get to some place, we would know where each road leads to. For instance a map.
If we didn’t know (unknown TE), we would have to randomize, which is a brute force solution, that rarely work on large cases.
What is the 4-phase problem solving strategy?
1) Goal formulation. The agent receives a goal. This will limit the behavior to concentrate on this goal only. This will reduce the total amount of possible actions.
2) Problem formulation. The agent devices a description of the states and actions necessary to reach the goal.
3) Search. Simulation of sequences of actions. When it finds a solution-sequence, it stops.
4) Executions. One action at a time.
When we have a fully observable, deterministic, known environment, what can we say about the solution?
the solution will always be a sequence of actions.
Define open-loop system?
A open loop system is a system that operates without receiving feedback during execution.
A open loop system is one where, after finding a solution from the search, you could ignore all other percepts. We know we will reach the goal, so there is no point in treating percepts.
If there is a change that the agent might not reach the goal, we would consider it a closed-loop system. Then we would monitor the percepts at all times.
In general terms, how can we describe a search problem?
We can describe a search problem by the following bullets:
1) State space (all possible states)
2) Initial state
3) set of goal states. Could be one, or many. Could be infinite.
4) Set of actions that are available
5) Transition model, describing what the actions does
6) An action cost function
What is the state space?
The state space is the space/set of all possible states that the environment can be in
What is the initial state, name example
Initial state is the state that we are currently in before choosing the path.
For instance, some place that we are currently at.
Elaborate on goal states
we could have one goal state, or we could have many. We would typically get many goal states if the goal is about reaching or satisfying some condition.
The goal state should be accompanied by a method called isGoal() that returns whether or not a state is a goal state.
Elaborate on the actions available to the agent
The actions that are available are dependent on the current state as well as the actuators of the agent.
Should have a method called “actions(s)” that gives a set of possible actions from this state.
Ex: actions(Arad) = {ToSibiu, ToTimisoara, ToZerind}
Elaborate on the transition model
The transition model describes what the actions does. Typically with the method called “result(s, a)” that gives the state that results from performing actions a on state s.
Therefore we can say that the transition model describes mappings from pairs of current state and some action, to some result state.
f: (s,a) —-> s’
Elaborate on the action cost function
We use the function “actionCost(s, a, s’)” to calculate the cost associated with performing action a on s to get to state s’. Typically, the lower the cost the better. Like shortest path. There should be heavy correlation between the action cost function the and performance measure of the agent.
We assume additivity. This means that the cost function applied on a series of states (path of size greater than 1) is simply the sum of individual costs.
What is the difference between standardized and real world problems?
Standardized problems are intended to illustrate the various problem solving methodology, and have a lot of performance benefits. However, these solutions are not generally used. Real life problems are idiosyncratic, which means that they require further specifications because they are individual.
Summary: Standardized problems are for methodology purposes
if we have a 2d array of square cells in which the agent can operate, what do we call this?
Grid world
Elaborate on what a “grid world” means
A grid world refers to a 2d array of squares in which an agent can operate. It serves as an abstraction of the world/environment. There are restrictions though, the square-assumptions being one.
A grid world is good for simplicity, but can quickly become large.
Explain how the vacuum world can be formulated as a grid world problem
We remember that a search problem can be formulated with 6 bullet points:
1) State space
2) Initial state
3) Goal state
4) Actions
5) Transition model
6) Action cost function
I the vacuum world, we get the following:
State space consists of all possible states that the world can be in. We have 2 tiles, making a 1x2 matrix. Since each tile can contain dirt independently of the other, we get 4 possible combinations of states. However, we also have the agent. The agent can be in either one of the tiles, regardless of whether the tile contains dirt or not. Therefore, we get n2^(n) = 22*2 = 8 possible states.
The initial state could be either one, doesn’t really matter.
Actions: We can suck, move left or move right. KEY DISTINCTION: Absolute vs egocentric actions. Absolute movement actions would be “up”, “down” etc. Egocentric actions are relative to the viewpoint of the agent. “Turn left”, “turn right” etc.
Transition model: We know that “suck” removes dirt. We know “forward” moves one tile forward in the direction that the agent face. etc.
Goal states: the state where every tile is clean. 2 of the 8 states in the state space are goal states.
Actions costs: Each action cost 1.
Define superimpose
To lay something over something else. In AI context, we can superimpose a search tree over the state space graph. Each node in the search tree corresponds to a state in the state space, and the edges represent the actions required to reach them.
What do we mean by “expanding” a node?
Expanding a node refers to finding new nodes by testing actions and finding out what nodes (states) they lead to. In other words, we use the result(s, a) function to see where an action leads to.
After generating new nodes, we now need to figure out which if the newly generated nodes to consider next. This is the essence of a search.
What is the “frontier” of the search tree?
The frontier is the list of unexpanded nodes in the tree. The nodes are reached, but not expanded.
We say that the frontier separates two parts of the state space graph.
1) The part that is expanded (discovered completely)
2) The part that is not yet reached
Describe best first search
Best first search searches for a solution by always choosing to expand nodes that are “cheapest”.
It use a priority queue with nodes that are sorted based on some evaluation function f(n). When it extract a node from the queue, it always gets the node with the lowest edge weight.
The also runs until the priority queue is empty or a solution is found.
IMPORTANT:
When BestFirstSearch expands a node, it will generate new nodes for the states we can reach by using the arsenal of actions from the state/node we are expanding. Each generated child will receive a COST. This cost is equal to the path-cost from the root to the node that we are expanding + the cost of going to from the expanding node to the newly generated node. So, cost=Path-Cost + Action-Cost.
The total cost to reach a node is thus subject to change if we find another route that leads to the same state but has a better total cost. In such a case, we need to add the child to the frontier AGAIN even though we already added it previously. This is because the new total cost may introduce new oppurtunities.
What do we need to create a data structure that represent states?
four parts.
1) node.STATE
2) node.PARENT
3) node.ACTIOn
4) node.PATH-COST
How do we, given a solution goal state, find the action sequence?
We use the parent pointers to chain backwards while keeping track of the action (stored in each node) that lead us to this specific state.
Name queues we can use
LIFO, FIFIO, priority
What is a “repeated state”?
A state that is reached multiple times. Cycles create such repeated states. Therefore, if one includes cycles, there is no end to the state space. We could continue to infinity.
What do we mean by redundant paths?
Redundant paths are paths that we need not consider because they offer a solution, but not a better solution that one we currently have. We are not interested in worse solutions.
We absolutely have to eliminate redundant paths! In larger cases (not even very large, 10x10 grid problems) redundant paths make it a million times slower.
Give a detailed explanation of best first search
the algorithms takes problem and a function f as input, and returns a goal node. When returned, the goal node contains a pointer to another node, which again points further, creating a chain of nodes which creates the solution path.
There are two engines in the best first algorithm:
1) Priority queue based on the function f(n).
2) Reached lookup table.
The priority queue is simple enough, and holds nodes that are on the frontier. The algorithm works by while-looping through the priority queue, iterating through the nodes on the frontier with the lowest value. Therefore, the way f(n) works will define the algorithm.
The look up table, typically a hash map structure, is key. It holds different “states” as Keys, and the corresponding value is the node. HERE IS THE IMPORTANT PART: A node is not the same as a node. Meaning, the expand-function generate nodes with different attribute values, even though it is the same node/state. Therefore, several nodes can have the same state, but they will typically have different parent nodes and different path cost. THIS is what drives the reached look up table.
THE PROCESS:
we extract the node from the priority queue with the lowest cost between it and the current node. Then an if statement checks whether we have reached the goal state or not. If so, return node. Else, continue.
Assuming we didn’t reach the goal, we now use the expand function to generate child nodes. These child nodes contain states like always, but they also contain root-specific parent nodes etc. Then we loop through all the newly generated child nodes, and find their states. If this state has never been previously reached, we will add the state in the look up table along with the node representing the state, and we add this node to the frontier.
If the node has been previously reached, we compare the path cost between the old way and the new way. If the new is better, we add the new node (with correct pointer/updated pointer information) to the frontier and update the look up table as well.
This is the general idea.
The “expand” function is used to generate child nodes. How does it work?
It receives a node, and then loops through all possible actions that may be performed at the given state.
s = node.state
for action in actions(s):
s’ = result(s,action)
cost = node.path-cost + problem.Action-cost(s, action, s’)
yield node(state = s’, parent=node, action=action, path-cost=cost)
What do we mean by “problem” that we see in the input of a search?
A problem is an abstract class (in python) that represents functionality that a problem must have.
Formally, a search problem contains the following:
1) a set of possible states, also known as the state space
2) The initial state
3) A set of goal states. Accompanied by the isGoal() method
4) The actions that are avaiable to the agent at a specific state
5) A transition model, using the result(s,a) function to figure out how our actions impact the world
6) An action-cost function. Calculate the cost of performing a certain action. Given by the Action-Cost(s,a,s’) if we are programming, or c(s,a,s’) if we’re doing math.
It contains functions that provide:
- actions, through a actions(state) method
- result method, gives you the state when a certain action is to be performed. Typically method result(state, action).
- goal_test(state)
- path_cost(state, action, result_state, costPrevious)
It is up to us, as programmers, to program a satisfactory subclass of the abstract class problem, so that it fits our problem.
Elaborate on “nodes”
Nodes are structures that mainly consists of pointers.
They point to their parent.
They point to the state that they represent.
Includes the action that got us to this node.
Contains the total path cost (from source).
The nodes do not have pointers to children. We find the children by using expand, which use actions and look at the state we get.
What is a “repeated state”?
A repeated state is a state that has been previously reached/expanded and then re-reached.
Can be because of cycles. If so, we may risk infinite states, so we need to be careful.
What is the meaning of redundant paths?
Redundant paths refer to the case where we have multiple/several paths that leads from the same source to the same goal. The path is different, but the endpoint and goal is the same for both paths.
We are typically only interested in the “best” paths, so there is no need to keep track of all of them. In fact, keeping track of all of them is a big problem due to the sheer size/number of paths we might have.
Consider 10x10 grid world and finding a path from a source tile to a goal tile. The number of possibilities would be ridiculous. We can’t keep track of all of them.
How do we eliminate redundant paths?
There are 3 ways:
1) Remember previously reached states. This way, we can compare the current best with alternatives and keep the better option. This is the approach used in best first search.
2) We could simply not give a fuck and dont check for redundancy. This works for problems where WE KNOW that redundancy is not an issue. For instance, when searching on structures that already have a tree-property, we need not worry. Assembly line for instance. We call a search that doesn’t check for redundancy a “tree-like search”. If it checks, we call it “graph search”.
3) We compromise and check for cycles, but not for redundant paths in general. We back trace and check for cycles.
In what ways can we measure performance of problem-solving algorithms?
There are 4 ways:
1) Completeness. Does it find a solution if one exists?
2) Cost optimality. Does it find the BEST solution?
3) Time complexity
4) Space complexity
What is branching factor?
Branching factor refers to the number of successors of a node that needs to be considered (the immediate children of a node)
When is the breadth first search appropriate?
Uninformed algorithm that works well when every action cost the same.
Can we use best first to calculate breadth-first search?
Yes, we can do this by using f(n)=amount of actions, and then perhaps multiply this number by a weight.
However, this is not the most efficient way of implementing a breadth first search.
What are the main differences between breadth first and best first in terms of “tricks” to improve efficiency?
Firstly, breadth first use a FIFO queue, which will always be faster than priority queues. FIFO is sufficient because we always add nodes according to their level away from the source.
Secondly, “reached” can be a set of states rather than a hash map. This is because if we reach a certain node, we know that the current path is the best, as every other path will be longer (because equal weights).
This also means that we can do an early goal test, in contrast to the late goal test that best first does.
What do we call Dijkstra’s in the AI community?
Uniform-cost search
Explain uniform-cost search
It is the exact same as best-first, but we use evaluation function as a function that calculates the total path cost from source to node.
The origin of the name “uniform” refers to the fact that this algorithm WILL always perform on nodes of same “weight”/”cost” in order.
is depth first search cost optimal?
No. It is not cost optimal because if will return the first solution it finds.
When do we consider using depth first search?
Depth first is great whenever the graph we are expanding is a tree like structure. Meaning, where a tree like search is feasible, the depth first search require much less memory than the other searches. This is because the frontier is very small, and the reached look up table is not included.
Compare memory requirements of the depth first search and the breadth first search
Breadth first search require a reachedtable that become increasingly large further down. very fast reach memory limits.
Depth first only keep the current path as frontier (and some other nodes).
Because of this. depth first search has become a workhorse of AI.
Depth first: O(bm)
Breadth first: O(b^d)
What are the requirements of using a depth first search?
finite state space.
In cyclic state spaces, it may get stuck in infinite loop, must therefore accommodate for such situations.
There are ways, however, that allowed us to use a depth first search even though the original state space is infinite. This method is called “depth limited search”.
What is the point of depth limited search?
We add a limit “L” that basically determines a certain depth where we simply dont consider the successors of nodes.
This obviously puts a lot of importance on choosing a suitable value for the depth limit.
What is the “diameter” of the state space?
The diameter of the state space refers to the max length we need to get from one side to the entire other side/all other points. If it can be proved that you only need 10 actions to reach every city in a country, then this diameter level would be a good depth limit. There is simply no point in looking further down, as the solutions that we could find further down will be even worse than the current ones.
When we dont know the diameter of the state space, what can we do if we still want to use DFS due to memory implications?
We can use the iterative deepening search.
The iterative deepening search picks/tries all values for the depth limit.
Explain, detailed, the Iterative deepening search
The iterative deepening search use many calls to “Depth limited search” with various/iterative values of depth limit.
The iterative part loops from 0 to infinity, each time calling the depth-limited-search. This returns the result. If the result is not equal to some cutoff value, then it returns and the method ends. But if the returned value from depth-limited-search is the cutoff value, then the loop continue.
In the depth-limited-search:
It takes input as the problem, and the depth limit. Problem is the same as with best first search.
It first create a LIFO queue, which is basically a stack. This is the engine, and represent the frontier. At the beginning, the initial state node is added.
Then it initialize the “result” variable as “failure”.
The main part of the search (at the current depth limit) is a while loop that runs through the stack (frontier). It extracts the top element of the stack/frontier, checks if this is the goal state or not (returns node is yes).
Then it checks if the depth of this node is greater than the depth limit. If this is true, then it sets the result variable equal to “cutoff”, and disregard the node, continuing the loop by extracting another element from the frontier stack.
But, if the node depth is not greater than the depth limit, then it runs a “is-not-Cycle(node)” method on the node. If not cycle, it expands the node, generating children of the node and adding them to the frontier. Then the while loop continues.
There is great focus on the is-cycle(node) method in order to avoid going backwards while trying to get deeper in the graph. If we detect a child node as a cycle, we simply ignore the node.
