Information-Based Alpha-Beta Seach and the Homicidal Chauffeur. Todd W. Neller. Hybrid Systems: Computation and Control. 2002

  1. Discusses why control techniques that may be locally optimal are often not globally optimal
  2. As title suggests, algorithm proposed is called Information-Based A-B Search
  3. The homicidal chauffeur (HC) is similar to the cat and mouse game, and is in the class of differential games
    1. The version of HC here is slightly different from the normal version (one way is that moves are not simultaneous)
  4. Major differences between this version and classic A-B search is:
    1. Because of the formalism used which involves a delay function (which I don’t really understand) the utility function is computed with an extra step, seems minor
    2. There is a continuum of actions to be selected from
    3. There is also a difference between the normal formalism of finding next states
  5. The action selection method used over the continuum of actions is in the class of max-likelihood optimization techniques, called information-based optimization
    1. The meat of the details is left to another paper
    2. Basic goal is that the algorithm starts with a target value.  At each step of optimization the algorithm evaluates the point most likely to have the value given the history
    3. The version they use assumes parabolic curves in between sample points, so the result is probably similar in character to gaussian process optimization
  6. Even though the action selection is computationally expensive, more efficiently searching the tree can easily compensate for this
    1. In empirical results they bear this out, as search size increases
    2. They see nearly exponential savings in wall time as search breadth increases against random action selection
      1. They have the opposite result for search depth, propose using random deeper in the tree
    3. When facing uniform action discretization they see exponential savings over uniform action discretization
  7. It would be neat to put FS3+HOO against this algorithm.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: