Map construction
Agents must not only visit every node but output a map of the anonymous graph, up to isomorphism.
Problem statement and measuresexpand
Agents explore an unknown anonymous port-labelled graph and must output a map: a port-labelled graph, kept in the agent's memory, that is isomorphic to the explored graph (with the ports), with the agent's current node indicated. Time is the number of moves.
Measures: Cost, moves until the map is built.
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Cost
Agents + static graph, + undirected
—
unknown
\(O(N^6\Delta^2\log N)\) vs —
unknown
\(O(mn)\) vs —
unknown
\(\text{finite}\) vs \(\text{impossible}\)
symmetry
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.