Navigability with Imperfect Information
This addresses theoretical limitations in AI navigation for agents with imperfect information, but it is incremental as it builds on prior work about perfect recall.
The paper tackles the problem of autonomous agent navigability in mazes with indistinguishable rooms, showing that a new notion of restricted navigability restores a form of transitivity even for agents without perfect recall, with the main result being a sound and complete logical system describing its properties.
The article studies navigability of an autonomous agent in a maze where some rooms may be indistinguishable. In a previous work the authors have shown that the properties of navigability in such a setting depend on whether an agent has perfect recall. Navigability by an agent with perfect recall is a transitive relation and without is not transitive. This article introduces a notion of restricted navigability and shows that a certain form of transitivity holds for restricted navigability, even for an agent without perfect recall. The main technical result is a sound and complete logical system describing the properties of restricted navigability.