column

Computational geometry column 59

Authors:

Adrian Dumitrescu,

Csaba D. TóthAuthors Info & Claims

ACM SIGACT News, Volume 45, Issue 2

Pages 68 - 72

https://doi.org/10.1145/2636805.2636822

Published: 09 June 2014 Publication History

Get Access

Abstract

This column is about patrolling problems in a geometric network. Mobile agents patrol a road network, and have to visit every point in the network as frequently as possible. The goal is finding a schedule that minimizes the idle time, i.e., the maximum time between two consecutive visits of some agent over all points in the network.

References

[1]

N. Agmon, S. Kraus, and G. A. Kaminka, Multi-robot perimeter patrol in adversarial settings, in Proc. International Conference on Robotics and Automation (ICRA 2008), IEEE, 2008, pp. 2339--2345.

Crossref

Google Scholar

[2]

J. Barajas and O. Serra, The lonely runner with seven runners, Electronic Journal of Combinatorics 15(1) (2008), R48.

Crossref

Google Scholar

[3]

T. Bohman, R. Holzman, and D. Kleitman, Six lonely runners, Electronic Journal of Combinatorics 8 (2001), R3.

Crossref

Google Scholar

[4]

Y. Chevaleyre, Theoretical analysis of the multi-agent patrolling problem, in Proc. International Conference on Intelligent Agent Technology (IAT 2004), IEEE, 2004, pp. 302--308.

Digital Library

Google Scholar

[5]

H. Choset, Coverage for robotics|a survey of recent results, Annals of Mathematics and Artificial Intelligence 31 (2001), 113--126.

Digital Library

Google Scholar

[6]

A. Collins, J. Czyzowicz, L. Gasieniec, A. Kosowski, E. Kranakis, D. Krizanc, R. Martin and O. M. Ponce, Optimal patrolling of fragmented boundaries, in Proc. 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013), ACM, 2013, pp. 241--250.

Digital Library

Google Scholar

[7]

T. W. Cusick, View-obstruction problems, Aequationes Math. 9 (1973), 165--170.

Crossref

Google Scholar

[8]

T. W. Cusick and C. Pomerance, View-obstruction problems III, Journal of Number Theory 19 (1984), 131--139.

Crossref

Google Scholar

[9]

J. Czyzowicz, L. Gasieniec, A. Kosowski, and E. Kranakis, Boundary patrolling by mobile agents with distinct maximal speeds, in Proc. 19th European Symposium on Algorithms (ESA 2011), LNCS 6942, Springer, 2011, pp. 701--712.

Digital Library

Google Scholar

[10]

A. Dumitrescu, A. Ghosh, and Cs. D. Tóth, On fence patrolling by mobile agents, preprint, January 2014; arXiv:1401.6070.

Google Scholar

[11]

Y. Elmaliach, N. Agmon, and G. A. Kaminka, Multi-robot area patrol under frequency constraints, in Proc. International Conference on Robotics and Automation (ICRA 2007), IEEE, 2007, pp. 385--390.

Crossref

Google Scholar

[12]

A. Kawamura and Y. Kobayashi, Fence patrolling by mobile agents with distinct speeds, in Proc. 23rd International Symposium on Algorithms and Computation (ISAAC 2012), LNCS 7676, Springer, 2012, pp. 598--608.

Crossref

Google Scholar

[13]

A. Machado, G. Ramalho, J. D. Zucker, and A. Drogoul, Multi-agent patrolling: an empirical analysis of alternative architectures, 3rd International Workshop on Multi-Agent-Based Simulation, Springer, 2002, pp. 155--170.

Digital Library

Google Scholar

[14]

J. M. Wills, Zwei Sátze über inhomogene diophantische Approximation von Irrationalzahlen, Monatshefte für Mathematik 71(3) (1967), 263--269.

Crossref

Google Scholar

Cited By

View all

Kawamura ASoejima M(2020)Simple strategies versus optimal schedules in multi-agent patrollingTheoretical Computer Science10.1016/j.tcs.2020.07.037Online publication date: Aug-2020
https://doi.org/10.1016/j.tcs.2020.07.037
Dumitrescu ATóth C(2020)Problems on track runnersComputational Geometry10.1016/j.comgeo.2020.101611(101611)Online publication date: Feb-2020
https://doi.org/10.1016/j.comgeo.2020.101611
Gorain BMandal P(2019)Approximation Algorithms for Barrier Sweep CoverageInternational Journal of Foundations of Computer Science10.1142/S012905411950013830:03(425-448)Online publication date: 30-Apr-2019
https://doi.org/10.1142/S0129054119500138
Show More Cited By

Index Terms

Computational geometry column 59

Recommendations

Boundary patrolling by mobile agents with distinct maximal speeds
ESA'11: Proceedings of the 19th European conference on Algorithms

A set of k mobile agents are placed on the boundary of a simply connected planar object represented by a cycle of unit length. Each agent has its own predefined maximal speed, and is capable of moving around this boundary without exceeding its maximal ...
Single machine scheduling with release dates and job delivery to minimize the makespan

In single machine scheduling with release dates and job delivery, jobs are processed on a single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at ...
Minimising makespan for two batch-processing machines with non-identical job sizes in job shop

In this article, the job shop scheduling problem with two batch-processing machines is considered. The machines have limited capacity and the jobs have non-identical job sizes. The jobs are processed in batches and the total size of each batch cannot ...

Comments

Information & Contributors

Information

Published In

ACM SIGACT News Volume 45, Issue 2

June 2014

100 pages

ISSN:0163-5700

DOI:10.1145/2636805

Editor:
Brendan Mumey
Montana State University

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2014

Published in SIGACT Volume 45, Issue 2

Check for updates

Author Tags

Qualifiers

Column

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
81
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kawamura ASoejima M(2020)Simple strategies versus optimal schedules in multi-agent patrollingTheoretical Computer Science10.1016/j.tcs.2020.07.037Online publication date: Aug-2020
https://doi.org/10.1016/j.tcs.2020.07.037
Dumitrescu ATóth C(2020)Problems on track runnersComputational Geometry10.1016/j.comgeo.2020.101611(101611)Online publication date: Feb-2020
https://doi.org/10.1016/j.comgeo.2020.101611
Gorain BMandal P(2019)Approximation Algorithms for Barrier Sweep CoverageInternational Journal of Foundations of Computer Science10.1142/S012905411950013830:03(425-448)Online publication date: 30-Apr-2019
https://doi.org/10.1142/S0129054119500138
Gorain BMandal P(2015)Approximation algorithm for sweep coverage on graphInformation Processing Letters10.1016/j.ipl.2015.03.011115:9(712-718)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.ipl.2015.03.011
Kawamura ASoejima M(2015)Simple Strategies Versus Optimal Schedules in Multi-agent PatrollingProceedings of the 9th International Conference on Algorithms and Complexity - Volume 907910.1007/978-3-319-18173-8_19(261-273)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1007/978-3-319-18173-8_19

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Boundary patrolling by mobile agents with distinct maximal speeds

Single machine scheduling with release dates and job delivery to minimize the makespan

Minimising makespan for two batch-processing machines with non-identical job sizes in job shop

Comments

Information

Published In

Publisher

Publication History

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations