Week 2 - Reading

Chapter 3


  • This chapter talks about various problems that an agent faces and various ways to formulate the problem.
  • It explains different problems based on different scenarios and explains effective ways to come up with a search strategy to solve the problem.
  • It explains the formulate, search, execute design.
  • There are four essentially different types of problems — single state problems, multiple-state problems, contingency problems, and exploration problems.
  • The initial state, operator set, goal test, and path cost function define a problem. 
  • The process of removing detail from a representation is called abstraction.
  • Explains various toy problems and how to solve them.
  • A state is arc-consistent j if every variable has a value in its domain that is consistent with each of the constraints on that I variable. 

Chapter 4

  • This chapter takes the problems from the previous chapter and explains various ways of solving them.
  • It explains various algorithms and how each algorithm tackles the problem differently.
  • In order to focus the search, the measure must incorporate some estimate of the cost of the path from a state to the closest goal stat
  • A function that calculates such cost estimates is called a heuristic function, and is usually denoted by the letter h
  • With a good heuristic function, the space and time complexity can be reduced substantially. 
  • The restriction is to choose an h function that never overestimates the cost to reach the goal. Such an h is called an admissible heuristic
  • The catch is that, for most problems, the number of nodes within the goal contour search space is still exponential in the length of the solution.
  • the distance we will count is the sum of the horizontal and vertical distances. This is sometimes called the city block distance or Manhattan distance.
  • A problem with less restrictions on the operators is called a relaxed problem
  • ABSOLVER generated a new heuristic for the 8-puzzle better than any existing heuristic, and found the first useful heuristic for the famous Rubik's cube puzzle.
  • Iterative deepening is a useful technique for reducing memory requirements
  • The time complexity of IDA* depends strongly on the number of different values that the heuristic function can take on
  • SMA* (Simplified Memory-Bounded A*) algorithm, which can make use of all available memory to carry out the search. Using more memory can only improve search efficiency—one could always ignore the additional space, but usually it is better to remember a node than to have to regenerate it when needed. 
  • SMA* is the most complicated search algorithm we have seen yet.
  • Random-restart hill-climbing does just this: it conducts a series of hill-climbing searches from randomly generated initial states, running each until it halts or makes no discernible progress..

Comments

Post a Comment

Popular posts from this blog

Week 7 - Reading

Chapter 20 This kind of feedback is called a reward, or reinforcement. In games like chess, the  reinforcement is received only at the end of the game.  We call this a terminal state in the state history sequence.  The agent can be a passive learner or an active learner. A passive learner simply watches the world going by, and tries to learn the utility of being in various states; an active learner must also act using the learned information, and can use its problem generator to suggest explorations of unknown portions of the environment.  The agent learns an action-value function giving the expected utility of taking a given action in a given state. This is called Q-learning.  We define the reward-to-go of a state as the sum of the rewards from that state until a terminal state is reached. Given this definition, it is easy to see that the expected utility of a state is the expected reward-to-go of that state.  A simple method for updating uti...
Read more

Week 5 - Reading

Chapter 14 Agents almost never have access to the whole truth about their environment. The right thing to do, the rational decision, therefore, depends on both the relative importance of various goals and the likelihood that, and degree to which, they will be achieved. Probability provides a way of summarizing the uncertainty that comes from our laziness and ignorance. Probability theory makes the same ontological commitment as logic, namely, that facts either do or do not hold in the world. Degree of truth, as opposed to degree of belief, is the subject of fuzzy logic. Prior or unconditional probability; after the evidence is obtained, we talk about posterior or conditional probability. An agent is rational if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action If Agent 1 expresses a set of degrees of belief that violate the axioms of probability theory then there is a betting strategy for Agent 2...
Read more