Explorative Probabilistic Planning with Unknown Target Locations

Motion planning in an unknown environment such as Mars or underwater ocean demands synthesis of an optimal control policy that balances between exploration and exploitation. In this project, we present the environment as a labeled graph where the labels of states are initially unknown, and consider a motion planning objective to fulfill a generalized reach-avoid specification given on these labels in minimum time. 

1. We translate our problem to a Canadian traveler problem on an adapted state space by describing the record of visited labels as an automaton using a given LTL specification. 

2. We propose a strategy that enables the agent to perform its task by exploiting possible a priori knowledge about the labels and the environment and incrementally revealing the environment online.

3. We assigning edge weights for the adapted graph that balance between exploration and exploitation, given the current knowledge of the environment. 

4. We illustrate our strategy on the setting of an agent operating on a two-dimensional grid environment.