A mobile agent, modeled as a deterministic finite automaton, has to explore a convex terrain in the plane. The agent starts at an unknown point of the terrain and makes a series of moves. Before each move it takes a snapshot, which is the part of the terrain included in the disc of radius 1 centered at the current position of the agent. This snapshot is an input that causes the agent to possibly change state and make the next move in a chosen direction at a chosen distance less than 1, inside the terrain. The agent explores the terrain if every point of it can be eventually “seen” by the agent, i.e., is eventually in some snapshot. For many convex terrains, such exploration is impossible without marking the terrain in any way. Hence we allow the agent to use movable pebbles. A pebble can be dropped, subsequently seen by the agent if it returns to it, and possibly picked again. We consider the problem of what is the minimum number of pebbles sufficient for an agent to explore convex terrains. Our main result is a complete solution of this problem. We classify all convex terrains into five types, depending on whether the terrain contains a (infinite straight) line and whether it is bounded. For each of these types, we determine the minimum number of pebbles sufficient for exploration of all terrains of a given type. The agent is given the type of the terrain but does not know in which terrain of the given type it is operating and does not know its starting point. In all cases we determine the minimum number of pebbles sufficient for exploration. Each result has two parts. In the positive part, we design an algorithm that explores all terrains of a given type by an agent, using a given number of pebbles. In the negative part, we show that no agent using fewer pebbles can explore all terrains of the given type.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Exploration of Convex Terrains by a Deterministic Automaton with Pebbles

  • Mohamed Anouar Baaziz,
  • Andrzej Pelc

摘要

A mobile agent, modeled as a deterministic finite automaton, has to explore a convex terrain in the plane. The agent starts at an unknown point of the terrain and makes a series of moves. Before each move it takes a snapshot, which is the part of the terrain included in the disc of radius 1 centered at the current position of the agent. This snapshot is an input that causes the agent to possibly change state and make the next move in a chosen direction at a chosen distance less than 1, inside the terrain. The agent explores the terrain if every point of it can be eventually “seen” by the agent, i.e., is eventually in some snapshot. For many convex terrains, such exploration is impossible without marking the terrain in any way. Hence we allow the agent to use movable pebbles. A pebble can be dropped, subsequently seen by the agent if it returns to it, and possibly picked again. We consider the problem of what is the minimum number of pebbles sufficient for an agent to explore convex terrains. Our main result is a complete solution of this problem. We classify all convex terrains into five types, depending on whether the terrain contains a (infinite straight) line and whether it is bounded. For each of these types, we determine the minimum number of pebbles sufficient for exploration of all terrains of a given type. The agent is given the type of the terrain but does not know in which terrain of the given type it is operating and does not know its starting point. In all cases we determine the minimum number of pebbles sufficient for exploration. Each result has two parts. In the positive part, we design an algorithm that explores all terrains of a given type by an agent, using a given number of pebbles. In the negative part, we show that no agent using fewer pebbles can explore all terrains of the given type.