Exploring Unknown Environments
From MaRDI portal
Publication:4943862
DOI10.1137/S009753979732428XzbMath0947.68165MaRDI QIDQ4943862
Susanne Albers, Monika R. Henzinger
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)
Related Items (73)
An improved lower bound for competitive graph exploration ⋮ OPTIMAL CONSTRUCTION OF SENSE OF DIRECTION IN A TORUS BY A MOBILE AGENT ⋮ Fault-tolerant sequential scan ⋮ Energy-Optimal Broadcast in a Tree with Mobile Agents ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Collaborative Exploration by Energy-Constrained Mobile Robots ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ Collision-free network exploration ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ Exploring a dynamic ring without landmark ⋮ Online graph exploration on trees, unicyclic graphs and cactus graphs ⋮ The ANTS problem ⋮ Searching without communicating: tradeoffs between performance and selection complexity ⋮ Distributed exploration of dynamic rings ⋮ Online graph exploration: New results on old and new algorithms ⋮ Exploration of Time-Varying Connected Graphs with Silent Agents ⋮ Evacuating two robots from multiple unknown exits in a circle ⋮ Grid exploration by a swarm of autonomous robots with minimum repetitions ⋮ Efficient live exploration of a dynamic ring with mobile robots ⋮ Distributed algorithms for filling MIS vertices of an arbitrary graph by myopic luminous robots ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ How many ants does it take to find the food? ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Search on a Line by Byzantine Robots ⋮ Approximate sequencing for variable length tasks. ⋮ Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots ⋮ Algorithms for \(p\)-Faulty Search on a half-line ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Predicting the labels of an unknown graph via adaptive exploration ⋮ Drawing maps with advice ⋮ Exploration of Faulty Hamiltonian Graphs ⋮ Deterministic network exploration by a single agent with Byzantine tokens ⋮ Searching for a black hole in arbitrary networks: optimal mobile agents protocols ⋮ Priority evacuation from a disk: the case of \(n \geq 4\) ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Building a nest by an automaton ⋮ Fast periodic graph exploration with constant memory ⋮ Map construction of unknown graphs by multiple agents ⋮ Setting port numbers for fast graph exploration ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Impact of memory size on graph exploration capability ⋮ Online Graph Exploration: New Results on Old and New Algorithms ⋮ GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST ⋮ Tree exploration with advice ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ Gossiping by energy-constrained mobile agents in tree networks ⋮ Remembering without memory: tree exploration by asynchronous oblivious robots ⋮ Search on a line with faulty robots ⋮ Optimal graph exploration without good maps ⋮ Unnamed Item ⋮ Anonymous graph exploration without collision by mobile robots ⋮ Broadcast in the rendezvous model ⋮ Exploring a Dynamic Ring Without Landmark ⋮ Weighted nearest neighbor algorithms for the graph exploration problem on cycles ⋮ Collaborative exploration of trees by energy-constrained mobile robots ⋮ A general lower bound for collaborative tree exploration ⋮ Beachcombing on strips and islands ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Using a collective of agents for exploration of undirected graphs ⋮ Collaborative delivery with energy-constrained mobile robots ⋮ Learning Unknown Graphs ⋮ Communication Problems for Mobile Agents Exchanging Energy ⋮ More Efficient Periodic Traversal in Anonymous Undirected Graphs ⋮ Group search of the plane with faulty robots ⋮ Energy-optimal broadcast and exploration in a tree using mobile agents ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Graph exploration by a finite automaton ⋮ Weighted group search on a line \& implications to the priority evacuation problem ⋮ Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics ⋮ Exploring sparse graphs with advice ⋮ Performance bounds for planning in unknown terrain ⋮ Graph exploration by energy-sharing mobile agents
This page was built for publication: Exploring Unknown Environments
