Lune

SODA2020顶会

Navigating an Infinite Space with Unreliable Movements

Anders Martinsson, Jara Uitto

摘要

We consider a search problem on a 2-dimensional infinite grid with a single mobile agent. The goal of the agent is to find her way home, which is located in a grid cell chosen by an adversary. Initially, the agent is provided with an infinite sequence of instructions, that dictate the movements performed by the agent. Each instruction corresponds to a movement to an adjacent grid cell and the set of instructions can be a function of the initial locations of the agent and home. The challenge of our problem stems from faults in the movements made by the agent. In every step, with some constant probability 0 p 1, the agent performs a random movement instead of following the current instruction.

This paper provides two results on this problem. First, we show that for some values of p, there does not exist any set of instructions that guide the agent home in finite expected time. Second, we complement this impossibility result with an algorithm that, for sufficiently small values of p, yields a finite expected hitting time for home. In particular, we show that for any p < 1, our approach gives a hitting rate that decays polynomially as a function of time. In that sense, our approach is far superior to a standard random walk in terms of hitting time. The main contribution and take-home message of this paper is to show that, for some value of 0.01139 • • • < p < 0.6554 . . ., there exists a phase transition on the solvability of the problem.

问 Lune

几分钟读透这篇 Paper,不用再花一下午。

Lune 能读完全文,也能读引用它的顶会 Paper,讲清它的结论、证据和局限,每一点都注明出自哪篇 Paper。不用硬啃,也不靠猜。

可以从这些问题问起

Lune 可以查阅

全文 · 相关的 Paper

获取答案

免费开始,无需绑卡

相关 Paper

  1. Competitive Strategies for Symmetric Rendezvous on the LineMax Klimm, Guillaume Sagnol, Martin Skutella, Khai Van TranSODA 2022 · 1 次引用
  2. Online Search with Maximum ClearanceSpyros Angelopoulos, Malachi VossAAAI 2021 · 2 次引用
  3. Navigating to the Best Policy in Markov Decision ProcessesAymen Al Marjani, Aurélien Garivier, Alexandre ProutièreNeurIPS 2021 · 34 次引用
  4. MeshA*: Efficient Path Planning with Motion PrimitivesMarat Agranovskiy, Konstantin YakovlevAAAI 2026
  5. Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic RegionsDaniel Platnick, Dawson Tomasz, Eamon Earl, Sourena Khanzadeh 等AAAI 2026
黄昏的海面,两侧是细线勾勒的悬崖