In robotics and autonomous systems, effective planning requires an accurate model of the environment. However, real-world "rules" are often uncertain and vary based on the agent's state. For instance, a drone's GPS reliability might depend on its proximity to specific structures. This paper introduces a framework to learn these transition models online using Incremental Feature Dependency Discovery (iFDD), enabling high performance in massive state spaces with minimal samples.
The Adaptive Planning Framework
The core of the proposed approach is an iterative loop that bridges real-world interaction and internal simulation. The agent starts with an approximate model, plans a policy within a simulator, executes that policy in the real world, and uses the resulting observations to refine its model parameters.
As shown in Figure 1, the process involves four main components: the Environment, the Parameter Estimator, the Simulator, and the Planner. The Parameter Estimator uses $n$ samples from the environment to update model parameters. The Simulator then uses these parameters to provide $N_{plan}$ interactions for the Planner, which finally executes $N_{exec}$ actions in the real world to close the loop.
Incremental Feature Dependency Discovery (iFDD)
To handle large state spaces without the exponential growth of tabular methods, the authors utilize iFDD integrated with Stochastic Gradient Descent (SGD). Instead of pre-defining all possible state dependencies, iFDD starts with basic atomic features. When the agent observes consistent estimation errors where multiple features are active simultaneously, iFDD automatically creates "conjunctive" features. This allows the model to grow its representation only where necessary, balancing early generalization with late-stage resolution.
Efficient Planning via TBVI
For planning within the simulator, the framework employs Trajectory-Based Value Iteration (TBVI). Unlike standard Value Iteration, TBVI focuses updates on states the agent is actually likely to visit. This focus is critical for scaling to complex domains like Persistent Search and Track (PST), which contains approximately 19 million state-action pairs. By focusing computational power on reachable states, TBVI makes massive problems tractable.
Experimental Evaluation and Results
The framework was evaluated across three increasingly complex simulated environments:
- Gridworld Navigation: Successfully learned localized spatial "danger zones" where GPS failure rates were high.
- Block Building: Outperformed tabular methods by quickly mastering non-linear collapse probabilities based on tower height and support blocks.
- Persistent Search and Track (PST): In this 19-million-state domain, iFDD was roughly 2.5 times more sample-efficient than tabular estimation. It achieved near-optimal performance using only 10,000 features—a 70x reduction in model size compared to a tabular format.
Conclusion
By leveraging the sparsity of complex dependencies in the real world, iFDD provides a scalable solution for model-based Reinforcement Learning in uncertain environments. While the current implementation focuses on state-dependent uncertainties, the framework's success in high-fidelity simulations demonstrates its potential for complex, real-world autonomous missions where environment dynamics are not fully known a priori.
Summary updated