I detta dokument överväger vi problemet med att planera en väg för en robot att övervaka en känd uppsättning funktioner av intresse för en miljö. Vi representerar miljön som en graf med vertex vikter och kantlängder. De hörn representerar regioner av intresse, kant längder ger restider mellan regioner och vertex vikter ger betydelsen av varje region. När roboten gång på gång utför en sluten gång på grafen definierar vi den viktade latensen hos en vertex som är den maximala tiden mellan besök på vertex, viktad av betydelsen (vertexvikt) av vertex. Vårt mål är att hitta en sluten promenad som minimerar den maximala viktade latensen av någon vertex. Vi visar att det inte finns någon polynomalgoritm för problemet. Vi tillhandahåller sedan två approximationsalgoritmer; en O( log n) - approximationsalgoritm och en O( log ρ G ) - approximationsalgoritm, där ρ G är förhållandet mellan maximal och minsta vertex-vikter. Vi tillhandahåller simuleringsresultat som visar att våra algoritmer kan tillämpas på problem som består av tusentals hörn och en fallstudie för att patrullera en stad för brott.
Alamdari m.fl. REF representerar miljön som en graf med vertex vikter och kantlängd och kartlägger det ihållande övervakningsproblemet i problemet med att hitta ett sätt som minimerar den maximala viktade latensen hos alla vertex.
Persistent monitoring in discrete environments: Minimizing the maximum weighted latency between observations
{'venue': None, 'journal': 'The International Journal of Robotics Research', 'mag_field_of_study': ['Mathematics', 'Computer Science']}