Exploring Unkown Environments with Real-Time Search or RL. Sven Koenig


  1. Interested in control methods that interleave planning and plan execution in unknown environments.
  2. Based on agent-centered search, which restricts the search to the region of the environment that can be reached from the current state in a certain number of steps.
  3. At the time of writing, the most important algorithm in this area was LRTA* – Learning Real-Time A*, which has some good properties:
    1. Theoretical guarantees
    2. Is an any-time algorithm
    3. Can leverage heuristics
    4. Can be “interrupted” in execution; isn’t disrupted if it gets moved off trajectory
    5. Amortizes search over several episodes
  4. Interested in navigation domains that can be described as topo-maps, reaching the goal state in that setting
  5. Does forward search from a state and updates the expected (optimistic) distance from each state in the region to a (potential) goal state
  6. Shows LRTA* in unknown environments is worse than depth-first search (although by just a small amount)
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: