Of robot ants and elephants

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Of robot ants and elephants

Full text

Pdf (235 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1 table of contents

Budapest, Hungary

SESSION: Multi-robotics table of contents

Pages 81-88

Year of Publication: 2009

ISBN:978-0-9817381-6-1

Authors

Asaf Shiloni	Bar Ilan University, Israel
Noa Agmon	Bar Ilan University, Israel
Gal A. Kaminka	Bar Ilan University, Israel

Sponsors

: The Foundation for Intelligent Physical Agents
Microsoft Research : Microsoft Research
: Wiley - Blackwell Ltd
: Whitestein Technologies
: European Office of Aerospace Research and Development, Air Force Office of Scientific Research, United States Air Force Research Laboratory
: Drexel University

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 51, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

Investigations of multi-robot systems often make implicit assumptions concerning the computational capabilities of the robots. Despite the lack of explicit attention to the computational capabilities of robots, two computational classes of robots emerge as focal points of recent research: Robot Ants and robot Elephants. Ants have poor memory and communication capabilities, but are able to communicate using pheromones, in effect turning their work area into a shared memory. By comparison, elephants are computationally stronger, have large memory, and are equipped with strong sensing and communication capabilities. Unfortunately, not much is known about the relation between the capabilities of these models in terms of the tasks they can address. In this paper, we present formal models of both ants and elephants, and investigate if one dominates the other. We present two algorithms: AntEater, which allows elephant robots to execute ant algorithms; and ElephantGun, which converts elephant algorithms---specified as Turing machines---into ant algorithms. By exploring the computational capabilities of these algorithms, we reach interesting conclusions regarding the computational power of both models.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E. Şahin. Swarm robotics: From sources of inspiration to domains of application. In Swarm Robotics: SAB 2004 International Workshop, volume 3342 of Lecture Notes in Computer Science, pages 10--20. Springer, 2005.
	2	N. Hazon, F. Mieli, and G. A. Kaminka. Towards robust on-line multi-robot coverage. In ICRA, 2006.
	3	Sven Koenig , Yaxin Liu, Terrain coverage with ant robots: a simulation study, Proceedings of the fifth international conference on Autonomous agents, p.600-607, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376463]
	4	Sven Koenig , Boleslaw Szymanski , Yaxin Liu, Efficient and inefficient ant coverage methods, Annals of Mathematics and Artificial Intelligence, v.31 n.1-4, p.41-76, 2001 [doi>10.1023/A:1016665115585]
	5	Thomas H. Labella , Marco Dorigo , Jean-Louis Deneubourg, Division of labor in a group of robots inspired by ants' foraging behavior, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.1 n.1, p.4-25, September 2006 [doi>10.1145/1152934.1152936]
	6	Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
	7	Jason M. O'Kane , Steven M. Lavalle, Comparing the Power of Robots, International Journal of Robotics Research, v.27 n.1, p.5-23, January 2008 [doi>10.1177/0278364907082096]
	8	E. Osherovich, A. M. Bruckstein, and V. Yanovski. Covering a continuous domain by distributed, limited robots. In ANTS Workshop, pages 144--155, 2006.
	9	G. Prencipe. CORDA: Distributed coordination of a set of autonomous mobile robots. In ERSADS, pages 185--190, May 2001.
	10	R. Russell. Heat trails as short-lived navigational markers for mobile robots. In ICRA, volume 4, pages 3534--3539, 1997.
	11	R. Russell. Ant trails: An example for robots to follow? In ICRA, volume 4, pages 2698--2703, 1999.
	12	Amanda J. Sharkey, Robots, insects and swarm intelligence, Artificial Intelligence Review, v.26 n.4, p.255-268, December 2006 [doi>10.1007/s10462-007-9057-y]
	13	Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, 1996
	14	Ichiro Suzuki , Masafumi Yamashita, Distributed Anonymous Mobile Robots: Formation of Geometric Patterns, SIAM Journal on Computing, v.28 n.4, p.1347-1363, Aug. 1999 [doi>10.1137/S009753979628292X]
	15	R. M. Turner. The tragedy of the commons and distributed AI systems. In in Proceedings of the 12th International Workshop on Distributed Artificial Intelligence, pages 379--390, 1993.
	16	I. Wagner, M. Lindenbaum, and A. Bruckstein. Distributed covering by ant-robots using evaporating traces. IEEE Transactions on Robotics and Automation, 15(5):918--933, 1999.
	17	Israel A. Wagner , Yaniv Altshuler , Vladimir Yanovski , Alfred M. Bruckstein, Cooperative Cleaners: A Study in Ant Robotics, International Journal of Robotics Research, v.27 n.1, p.127-151, January 2008 [doi>10.1177/0278364907085789]
	18	Israel A. Wagner , Alfred M. Bruckstein, From Ants to A(ge)nts: A Special Issue on Ant-Robotics, Annals of Mathematics and Artificial Intelligence, v.31 n.1-4, p.1-5, 2001
	19	Vladimir Yanovski , Israel A. Wagner , Alfred M. Bruckstein, Vertex-Ant-Walk – A robust method for efficient exploration of faulty graphs, Annals of Mathematics and Artificial Intelligence, v.31 n.1-4, p.99-112, 2001 [doi>10.1023/A:1016688707365]