Towards a Second Generation Random Walk Planner: An Experimental Exploration. Nakhost, Muller. IJCAI 2013

  1. Focuses on best-first planners that use randomization to break out of regions of the search space that have a flat heuristic value
  2. Four major insights claimed
    1. Better to evaluate states frequently as opposed to just at the end of search
    2. Better to allow parameters to intelligently adjust on the fly
    3. Better to bias action selection based on current state as opposed to the simple heuristic of how useful it was throughout the entire history
    4. “Even simple forms of random walk planning can compete with GBFS.”
  3. Sat-searchers work almost exclusively based on heuristics.  IPC 2011 had 25 of 27 entries in that category.
    1. Because they use heuristics they don’t really explore; when heuristics are bad lack of search driven by other methods means that solution quality is poor
  4. The same authors, in 2009 introduced Monte-Carlo Random Walks, which run finite-length random walks, and then choose one course of action based on leaf evaluation
  5. Mention RRTs, as well as Roamer.
  6. The planner they discuss is called Arvand-2013, built on top of something called Fast Downward algorithm
  7. A fair amount of discussion of parameter values that worked well for particular different domains from IPC
  8. <Too results specific based on IPC domains, skipping>

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: