COLLABORATIVE EXPLORATION IN GRID DOMAINS - Constructive Conjecture of a Polynomial Time Complexity

Yaniv Altshuler, Alfred M. Bruckstein, Israel A. Wagner

2009

Abstract

This work discusses the problem of exploration of an unknown environment using a collaborative group of simple agents. While this problem was known to be of a non-polynomial time complexity, it was speculated in the past that in grid domains the completion time of this problem is much lower (although analytic proofs were not available hitherto). In this work we present a preliminary result concerning a constructive analytic constraint for guaranteeing that the time complexity of this problem in grid domains is indeed polynomial.

Paper Citation

in Harvard Style

Altshuler Y., M. Bruckstein A. and A. Wagner I. (2009). COLLABORATIVE EXPLORATION IN GRID DOMAINS - Constructive Conjecture of a Polynomial Time Complexity . In Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO, ISBN 978-989-8111-99-9, pages 252-257. DOI: 10.5220/0002214402520257

in Bibtex Style

@conference{icinco09,
author={Yaniv Altshuler and Alfred M. Bruckstein and Israel A. Wagner},
title={COLLABORATIVE EXPLORATION IN GRID DOMAINS - Constructive Conjecture of a Polynomial Time Complexity},
booktitle={Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO,},
year={2009},
pages={252-257},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002214402520257},
isbn={978-989-8111-99-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO,
TI - COLLABORATIVE EXPLORATION IN GRID DOMAINS - Constructive Conjecture of a Polynomial Time Complexity
SN - 978-989-8111-99-9
AU - Altshuler Y.
AU - M. Bruckstein A.
AU - A. Wagner I.
PY - 2009
SP - 252
EP - 257
DO - 10.5220/0002214402520257