  We consider several algorithms for exploring and filling an unknown,
connected region, by simple, airborne agents. The agents are assumed to be
identical, autonomous, anonymous and to have a finite amount of memory. The
region is modeled as a connected sub-set of a regular grid composed of square
cells. The algorithms described herein are suited for Micro Air Vehicles (MAV)
since these air vehicles enable unobstructed views of the ground below and can
move freely in space at various heights. The agents explore the region by
applying various action-rules based on locally acquired information Some of
them may settle in unoccupied cells as the exploration progresses. Settled
agents become virtual pheromones for the exploration and coverage process,
beacons that subsequently aid the remaining, and still exploring, mobile
agents. We introduce a backward propagating information diffusion process as a
way to implement a deterministic indicator of process termination and guide the
mobile agents. For the proposed algorithms, complete covering of the graph in
finite time is guaranteed when the size of the region is fixed. Bounds on the
coverage times are also derived. Extensive simulation results exhibit good
agreement with the theoretical predictions.
