Computer Science – Multiagent Systems
Scientific paper
2007-02-16
Computer Science
Multiagent Systems
15 pages, 8 figures
Scientific paper
An edge-colored directed graph is \emph{observable} if an agent that moves along its edges is able to determine his position in the graph after a sufficiently long observation of the edge colors. When the agent is able to determine his position only from time to time, the graph is said to be \emph{partly observable}. Observability in graphs is desirable in situations where autonomous agents are moving on a network and one wants to localize them (or the agent wants to localize himself) with limited information. In this paper, we completely characterize observable and partly observable graphs and show how these concepts relate to observable discrete event systems and to local automata. Based on these characterizations, we provide polynomial time algorithms to decide observability, to decide partial observability, and to compute the minimal number of observations necessary for finding the position of an agent. In particular we prove that in the worst case this minimal number of observations increases quadratically with the number of nodes in the graph. From this it follows that it may be necessary for an agent to pass through the same node several times before he is finally able to determine his position in the graph. We then consider the more difficult question of assigning colors to a graph so as to make it observable and we prove that two different versions of this problem are NP-complete.
Blondel Vincent D.
Jungers Raphael M.
No associations
LandOfFree
Observable Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Observable Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Observable Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-196300