Searching

• General introduction
  • The problem of finding path from a city called Arad to Bucharest
  • When you are formulating the problem the first thing we need to do is to establish the goal
  • Establish the resources. Cannot assume things such as you have a map.
• Vacuuming two rooms
  • The goal is to get to state 7 or 8
  • You may know full or partial information about the current state
  • You may not know anything about the current state
  • The sucking action may deposit dirt if there is no dirt
• Page 60: formal specifications for well defined problems and solutions
  • Initial state
  • The operators
  • The goal state
  • cost function associated with a path
  • Total cost is search cost + path cost
  • Total cost will be the motivating factor
• Section 3.3 uses some problems to explain the states, operators, goal test, path cost
• Route finding
  • An urban area network. We want to go from place A to place Y.
  • You have the map
  • Finding a path: Spanning tree
  • Travel distance/Travel time /Travel cost
  • A path with the least cost is the goal. Not necessarily shortest, not necessarily fastest
  • The costs may not be static, they may vary depending on whether you are travelling in the morning or in the afternoon or in the evening. This situation is still static
  • Semidynamic situation will be when the cost changes during your trip, but you know the cost ahead of time
  • The function of cost also changes during the travel
  • We cannot find the solution and stick to it throughout the execution. Interleaving of search and execution
  • Intelligent Vehicle Highway Systems
• Different strategies
• Page 73, section 3.5
  • Completeness: Is the strategy guranteed to find a solution
  • Time complexity: Time to do the search
  • space complexity
  • optimality: was it the best possible solution
• Different types of searches
  • Breadthfirst search
  • Depthfirst search
  • Uniform cost search
  • Expand all the nodes which have uniform cost
  • Figure 3.13
  • Breadthfirst search is the special case of uniform cost search
  • Depth-Limited search
    • Limit the depth to a certain number and start back tracking if you go up to that depth level
    • If there are 20 cities on a map, the depth limit should be 19
  • Iterative deepening search
    • Depth limit is increased iteratively
  • Bidirectional seacrh
    • This is possible only when parents can be derived from the children
• Constraint satisfaction problems
  • Most of the search strategies can staisfy constraints during the search
  • That is make sure that the solution that you are trying to find satisfies all the given conditions
  • In some situations special CSP techniques can work better than the normal seacrh techniques

Heuristic Search

• For every intermediate point in the path, we find out how close we are to the destination based on a heuristic function
• Kasparov and deep blue
  • Kasparov looks ahead two moves and decides how close a particular path
  • Let us say Kasporov considers 3000 possibilities and decides using a heuristic measure which one of the possibilities brings him close to the chek-mate in his favor
  • Deep blue will consider several billion? possibilities and uses a heuristic measure to decide how close it is to a check-mate in its favor
  • Obviously, his heuristic measure is better that its
  • better heuristic measure is an indication of intelligence
• Let us consider a couple of heuristic measures for 8-puzzle problem (pages 101-102)

Genetic Algorithms

• Pages 619-621:
  • A string of bits/features in the search strategy
  • Pick a number of arbtirary strings
  • Find out how far that search strategy took you from the destination
  • Pick top few (probably less than half) of the strategies
  • Then these chosen ones mate with each other
  • Mating two strings means take top half of one and combine with bottom half of the other and vice versa.
  • We don't have to go with 50-50 combination. You can go far 60-40, 70-30, etc.
  • The new genes that are created are again evaluated and the top ones are chosen
  • The process continues until you have found a string that will rpoduce the results
  • The problem with just using mating is that in some cases you may have several states around a certain local minima. Then these states will keep on reproducing and keep your search in and around your local minima. SO from time to time you mutate some of the strings. Flip one of the bits. Hopefully, mutation will take you off over that bump towards the global minima.