iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10514-010-9189-9
GSST: anytime guaranteed search | Autonomous Robots Skip to main content

Advertisement

Springer Nature Link
Log in

GSST: anytime guaranteed search

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

We present Guaranteed Search with Spanning Trees (GSST), an anytime algorithm for multi-robot search. The problem is as follows: clear the environment of any adversarial target using the fewest number of searchers. This problem is NP-hard on arbitrary graphs but can be solved in linear-time on trees. Our algorithm generates spanning trees of a graphical representation of the environment to guide the search. At any time, spanning tree generation can be stopped yielding the best strategy so far. The resulting strategy can be modified online if additional information becomes available. Though GSST does not have performance guarantees after its first iteration, we prove that several variations will find an optimal solution given sufficient runtime. We test GSST in simulation and on a human-robot search team using a distributed implementation. GSST quickly generates clearing schedules with as few as 50% of the searchers used by competing algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Alspach, B. (2006). Searching and sweeping graphs: a brief survey. Matematiche, 59, 5–37.

    MathSciNet  Google Scholar 

  • Barrière, L., Flocchini, P., Fraigniaud, P., & Santoro, N. (2002). Capture of an intruder by mobile agents. In Proc. 14th ACM symp. parallel algorithms and architectures (pp. 200–209).

  • Barrière, L., Fraigniaud, P., Santoro, N., & Thilikos, D. (2003). Searching is not jumping. Graph-Theoretic Concepts in Computer Science, 2880, 34–45.

    Google Scholar 

  • Bienstock, D., & Seymour, P. (1991). Monotonicity in graph searching. Journal of Algorithms, 12(2), 239–245.

    Article  MATH  MathSciNet  Google Scholar 

  • Char, J. (1968). Generation of trees, two-trees, and storage of master forests. IEEE Transactions on Circuit Theory, 15(3), 228–238.

    Article  MathSciNet  Google Scholar 

  • Dendris, N., Kirousis, L., & Thilikos, D. (1994). Fugitive-search games on graphs and related parameters. In Proc. 20th int. workshop graph-theoretic concepts in computer science (pp. 331–342).

  • Flocchini, P., Nayak, A., & Schulz, A. (2005). Cleaning an arbitrary regular network with mobile agents. In Proc. int. conf. distributed computing and Internet technology (pp. 132–142).

  • Flocchini, P., Huang, M., & Luccio, F. (2007). Decontamination of chordal rings and tori using mobile agents. International Journal of Foundations of Computer Science, 18(3), 547–564.

    Article  MATH  MathSciNet  Google Scholar 

  • Flocchini, P., Huang, M., & Luccio, F. (2008). Decontamination of hypercubes by mobile agents. Networks, 52(3), 167–178.

    Article  MATH  MathSciNet  Google Scholar 

  • Fomin, F., & Thilikos, D. (2008). An annotated bibliography on guaranteed graph searching. Theoretical Computer Science, 399, 236–245.

    Article  MATH  MathSciNet  Google Scholar 

  • Fomin, F., Fraigniaud, P., & Thilikos, D. (2004). The price of connectedness in expansions. Technical Report LSI-04-28-R, UPC Barcelona.

  • Fraigniaud, P., & Nisse, N. (2006). Connected treewidth and connected graph searching. In Proc. 7th Latin American symp. theoretical informatics.

  • Gerkey, B. (2004). Pursuit-evasion with teams of robots. http://ai.stanford.edu/~gerkey/research/pe/index.html.

  • Gerkey, B., Vaughan, R., & Howard, A. (2003). The player/stage project: tools for multi-robot and distributed sensor systems. In Proc. int. conf. advanced robotics (pp. 317–323).

  • Gerkey, B., Thrun, S., & Gordon, G. (2005). Parallel stochastic hill-climbing with small teams. In Proc. 3rd int. NRL workshop multi-robot systems.

  • Guibas, L., Latombe, J., LaValle, S., Lin, D., & Motwani, R. (1999). Visibility-based pursuit-evasion in a polygonal environment. International Journal of Computational Geometry and Applications, 9(5), 471–494.

    Article  MathSciNet  Google Scholar 

  • Hollinger, G., Kehagias, A., & Singh, S. (2009a). Efficient, guaranteed search with multi-agent teams. In Proc. robotics: science and systems conf.

  • Hollinger, G., Singh, S., Djugash, J., & Kehagias, A. (2009b). Efficient multi-robot search for a moving target. International Journal of Robotics Research, 28(2), 201–219.

    Article  Google Scholar 

  • Isler, V., Kannan, S., & Khanna, S. (2005). Randomized pursuit-evasion in a polygonal environment. IEEE Transactions on Robotics, 21(5), 875–884.

    Article  Google Scholar 

  • Kalra, N. (2006). A market-based framework for tightly-coupled planned coordination in multirobot teams. Ph.D. thesis, Robotics Institute, Carnegie Mellon Univ.

  • Kehagias, A., Hollinger, G., & Gelastopoulos, A. (2009a). Searching the nodes of a graph: theory and algorithms. Technical Report arXiv:0905.3359 [cs.DM].

  • Kehagias, A., Hollinger, G., & Singh, S. (2009b). A graph search algorithm for indoor pursuit/evasion. Mathematical and Computer Modelling, 50(9–10), 1305–1317.

    Article  MATH  MathSciNet  Google Scholar 

  • Kloks, T. (1994). Treewidth: computations and approximations. Berlin: Springer.

    MATH  Google Scholar 

  • Kolling, A., & Carpin, S. (2008). Extracting surveillance graphs from robot maps. In Proc. int. conf. intelligent robots and systems.

  • Kolling, A., & Carpin, S. (2010). Pursuit-evasion on trees by robot teams. IEEE Transactions on Robotics, 26, 32–47.

    Article  Google Scholar 

  • Kumar, V., Rus, D., & Singh, S. (2004). Robot and sensor networks for first responders. Pervasive Computing, 3(4), 24–33.

    Article  Google Scholar 

  • LaPaugh, A. (1993). Recontamination does not help to search a graph. Journal of ACM, 40(2), 224–245.

    Article  MATH  MathSciNet  Google Scholar 

  • LaValle, S. M. (2006). Planning algorithms. Cambridge: Cambridge University Press.

    Book  MATH  Google Scholar 

  • LaValle, S., Lin, D., Guibas, L., Latombe, J., & Motwani, R. (1997). Finding an unpredictable target in a workspace with obstacles. In Proc. IEEE international conf. robotics and automation.

  • Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., & Thrun, S. (2005). Anytime dynamic A*: an anytime, replanning algorithm. In Proc. int. conf. automated planning and scheduling.

  • Megiddo, N., Hakimi, S., Garey, M., Johnson, D., & Papadimitriou, C. (1988). The complexity of searching a graph. Journal of ACM, 35(1), 18–44.

    Article  MATH  MathSciNet  Google Scholar 

  • Parsons, T. (1976). Pursuit-evasion in a graph. In Y. Alavi, & D. Lick (Eds.) Theory and applications of graphs (pp. 426–441). Berlin: Springer.

    Google Scholar 

  • Shewchuk, J. (2002). Delaunay refinement algorithms for triangular mesh generation. Computational Geometry: Theory and Applications, 22(1–3), 21–74.

    MATH  MathSciNet  Google Scholar 

  • Smith, T. (2007). Probabilistic planning for robotic exploration. Ph.D. thesis, Robotics Institute, Carnegie Mellon Univ.

  • Wilson, D. (1996). Generating random spanning trees more quickly than the cover time. In Proc. 28th ACM symp. theory of computing (pp. 296–303).

  • Yang, B., Dyer, D., & Alspach, B. (2004). Sweeping graphs with large clique number. In Proc. 5th international symp. algorithms and computation (pp. 908–920).

  • Zilberstein, S. (1996). Using anytime algorithms in intelligent systems. Artificial Intelligence Magazine, 17(3), 73–86.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, 15217, USA

    Geoffrey Hollinger & Sanjiv Singh

  2. Faculty of Engineering, Aristotle University of Thessaloniki, Box 464, Thessaloniki, 54124, Greece

    Athanasios Kehagias

Authors
  1. Geoffrey Hollinger
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Athanasios Kehagias
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sanjiv Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Geoffrey Hollinger.

Electronic Supplementary Material

Below are the links to the electronic supplementary material.

(MP4 8,153 KB)

(MP4 5,321 KB)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hollinger, G., Kehagias, A. & Singh, S. GSST: anytime guaranteed search. Auton Robot 29, 99–118 (2010). https://doi.org/10.1007/s10514-010-9189-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-010-9189-9

Keywords

Search

Navigation