Compatibility of convergence algorithms for autonomous mobile robots
share
We consider several convergence problems for autonomous mobile robots under the SSYNC model. Let Φ and Π be a set of target functions and a problem, respectively. If the robots whose target functions are chosen from Φ always solve Π, we say that Φ is compatible with respect to Π. If Φ is compatible with respect to Π, every target function ϕ∈Φ is an algorithm for Π. Note that even if both ϕ and ϕ' are algorithms for Π, {ϕ, ϕ' } may not be compatible with respect to Π. We investigate, the convergence, the fault tolerant (n,f)-convergence (FC(f)), the fault tolerant (n,f)-convergence to f points (FC(f)-PO), the fault tolerant (n,f)-convergence to a convex f-gon (FC(f)-CP), and the gathering problem, assuming crash failures. We classify these problems from the viewpoint of compatibility; the group of the convergence, FC(1), FC(1)-PO and FC(f)-CP, and the group of the gathering and FC(f)-PO for f ≥ 2 have completely opposite properties. FC(f) for f ≥ 2 is placed in between.
READ FULL TEXT