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.