Abstract
In many real-world settings, an autonomous agent may not have sufficient information or sensory capabilities to accomplish its goals, even when they are achievable. In some cases, the needed information can be provided by another agent, but information sharing might be costly due to limited communication bandwidth and other constraints. We address the problem of Helpful Information Sharing (HIS), which focuses on selecting minimal information to reveal to a partially informed agent in order to guarantee it can achieve its goal. We offer a novel compilation of HIS to a classical planning problem, which can be solved efficiently by any off-the-shelf planner. We provide guarantees of optimality for our approach and describe its extensions to maximize robustness and support settings in which the agent needs to decide which sensors to deploy in the environment. We demonstrate the power of our approaches on a set of standard benchmarks as well as on a novel benchmark.
1. Introduction
Autonomous agents often operate with incomplete knowledge of their environment due to sensor limitations, occlusions, or communication failures. While a "helper" agent might possess the missing information, bandwidth constraints often prevent sharing the entire state. This research introduces the Helpful Information Sharing (HIS) framework, which aims to identify the minimal set of facts a helper must communicate to an actor to guarantee goal achievement.
2. Problem Formulation
The HIS problem involves an "actor" with a partial view of the world and a "helper" with more complete information. The goal is to find the smallest subset of facts that, when shared, allows the actor to plan a guaranteed path to its goal. This is critical in domains like underwater exploration or disaster response where communication is expensive or restricted.
3. Methodology
The authors propose two primary algorithmic approaches to solve the HIS problem:
3.1 Lazy Breadth-First Search (Lazy-BFS)
This method searches through the space of possible information subsets. To mitigate the combinatorial explosion of checking every fact combination, a "lazy" evaluation strategy is used. By checking relaxed versions of information sets first, the search can prune large branches of the state space that are guaranteed not to lead to a solution.
3.2 The $T_{ka}$ Compilation
The core contribution is a transformation that compiles the HIS problem into a standard fully observable classical planning problem.
- Information as Action: Sharing a specific fact is modeled as a physical action within the planning domain.
- Cost-Weighting: By assigning high costs to information-sharing actions relative to movement actions, the planner is incentivized to find a solution that minimizes communication. This compilation allows the use of state-of-the-art classical planners, such as Fast-Downward, to solve multi-agent coordination problems efficiently.
4. Experimental Evaluation
The methods were tested across seven domains, including standard benchmarks like WUMPUS and LOGISTICS, and a new domain called ESCAPE-ROOM.
4.1 Key Results
- Performance: The $T_{ka}$ compilation significantly outperformed BFS-based methods. In the LOGISTICS domain, $T_{ka}$ achieved a 100% success rate with an average solve time of 0.29 seconds, compared to 36 seconds for BFS.
- Scalability: In the complex COLOR-BALLS domain, $T_{ka}$ was the only method capable of solving the majority of instances within the time limit.
- Optimality: Empirical results confirmed that the cost-weighting strategy successfully identifies the mathematically minimal information set required for success.
5. Discussion and Future Work
While the $T_{ka}$ method is highly effective, it faces a "grounding bottleneck" in very large state spaces. Future research could investigate pruning techniques to reduce the size of the grounded representation. Additionally, extending the model to handle stochastic sensors (noisy data) and the cost of information acquisition for the helper would enhance its real-world applicability.
6. Conclusion
By framing information sharing as a classical planning task, this work provides a robust and efficient way to coordinate partially informed agents under strict communication constraints. The HIS framework ensures that agents receive exactly what they need to succeed, and nothing more.
Summary updated