Navigability with Imperfect Information
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Armstrong's Axioms and Navigation Strategies
The paper investigates navigability with imperfect information. It shows that the properties of navigability with perfect recall are exactly those captured by Armstrong's axioms from the database theory. If the assumptio…
validImproving Reachability and Navigability in Recommender Systems
In this paper, we investigate recommender systems from a network perspective and investigate recommendation networks, where nodes are items (e.g., movies) and edges are constructed from top-N recommendations (e.g., relat…
Recommendation SystemsLearning to Anneal and Prune Proximity Graphs for Similarity Search
This paper studies similarity search, which is a crucial enabler of many feature vector--based applications. The problem of similarity search has been extensively studied in the machine learning community. Recent advance…
Stochastic OptimizationInformation Cocoons in Online Navigation
Social media and online navigation bring us enjoyable experience in accessing information, and simultaneously create information cocoons (ICs) in which we are unconsciously trapped with limited and biased information. We…
Recommendation SystemsRetrievalNavigating temporal networks
Navigation on graphs is the problem how an agent walking on the graph can get from a source to a target with limited information about the graph. The information and the way to exploit it can vary. In this paper, we stud…