Envelope-based Planning in Relational MDPs

A mobile robot acting in the world is faced with a large amount of sensory dataand uncertainty in its action outcomes. Indeed, almost all interesting sequentialdecision-making domains involve large state spaces and large, stochastic action sets. We investigate a way to act intelligently asquickly as possible in domains where finding a complete policy would take a hopelessly long time. This approach, Relational Envelopebased Planning(REBP) tackles large, noisy problems along two axes.