Problem Definitions:

Rendezvous: A number of agents, in this case two, that start from distinct nodes of a ring need to meet in some node that is not known in advance.

(Collaborative) Exploration: A team of agents (say again two) need to visit each node of a ring within finite time. Each nodes needs to be visited by at least one agent.

I do not specify communication methods between agents, knowledge of initial distance, knowledge of the size of the ring and memory becasue I am interested in finding an answer for any scenario.

I have been reading this book that (among other things) gives lower bounds for the time needed for agents to rendezvous under various assumptions and after most time bounds an algorithm that satisfies these asumptions is given. The given algorithms also explore the ring but it is not stated if exploration is necessary or just convenient. Intuitively, I would expect that at least in the cases where the agents do not have much information about the network (such as initial distance to each other or knowledge of size) the ring will need to be explored, but I haven't been able to find a proof of that.

One (easy) result that I have been able to find is that if each node has a numerical ID and the agents have enough memory to read the label then rendezvous is reduced to exploration (e.g., by having the agents check all IDs and then move to the node with the smallest one). However, I am more interested in the necessity (or lack of necessity) of exploration for solving rendezvous and not of a reduction.

Are there any more general known results that connect collaborative exploration to rendezvous in a deterministic context?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.