2023/01/31 by Subhash Bhagat, Bhagat, Subhash, Andrzej Pelc +1
Computer Science · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mobile Agent-Based Network Management #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2302.00052
openalex publication_date 2023/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A mobile agent, modeled as a deterministic finite automaton, navigates in the infinite anonymous oriented grid ℤ × ℤ. It has to explore a given infinite subgraph of the grid by visiting all of its nodes. We focus on the simplest subgraphs, called \em wedges, spanned by all nodes of the grid located between two half-lines in the plane, with a common origin. Many wedges turn out to be impossible to explore by an automaton that cannot mark nodes of the grid. Hence, we study the following question: Given a wedge W, what is the smallest number p of (movable) pebbles for which there exists an automaton that can explore W using p pebbles? Our main contribution is a complete solution of this problem. For each wedge W we determine this minimum number p, show an automaton that explores it using p pebbles and show that fewer pebbles are not enough. We show that this smallest number of pebbles can vary from 0 to 3, depending on the angle between half-lines limiting the wedge and depending on whether the automaton can cross these half-lines or not.