The relationship between emergence of the shortest path and information value using ant-like agents

ABSTRACT

Ant-like agents forage between two points. These agents' probabilistic movements are based on the use of two pheromones; one marking trails towards the goal and another marking trails back to the starting point. Path selection decisions are influenced by the relative levels of attractive and repulsive pheromone in each agent's local environment. Our work in [5] evaluates three pheromone perception strategies, investigating path formation speed, quality, directionality, robustness and adaptability under different parameter settings(degree of randomness, pheromone evaporation rate and pheromone diffusion rate). We re-evaluate two of these strategies in terms of the amount of information they provide using Shannon's formulation [3, 4, 8, 9, 12, 14, 15, 16, 17]. We determine information as the difference between uncertainty before and after path selection decisions. Our focus in this paper is on investigating relationships between the emergence of the shortest path and the amount of stigmergic information that exists in the form of pheromone. Agents are deployed centrally and emergence measures are determined using the worst, reference and best cases observed in [5]. Additionally, the amount of local and global information that is available to agents in each movement step is evaluated. Furthermore, Pearson's correlation coefficients between measures of emergence and the amount of information are calculated. The significance of these correlation coefficients is tested using a 2 tailed test at 1% level of significance. Consequently the relationship between the amount of information and emergent behaviour is established. Significant relationships between information and the emergence of the shortest path exist when strong emergent behaviour is present.

REFERENCES

• 1: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 2: Stephen F. Bush and Amit B. Kulkarni. Active network management and kolmogorov complexity. In proceedings of the IEEE OpenArch 2001 Conference, 2001.
• 3: Tom Carter. An introduction to information theory and entropy. Complex Systems Summer Schools, June 2006.
• 4: Chaomei Chen, An Information-Theoretic View of Visual Analytics, IEEE Computer Graphics and Applications, v.28 n.1, p.18-23, January 2008 [doi>10.1109/MCG.2008.2]
• 5: Colin Chibaya , Shaun Bangay, A probabilistic movement model for shortest path formation in virtual ant-like agents, Proceedings of the 2007 annual research conference of the South African institute of computer scientists and information technologists on IT research in developing countries, p.9-18, October 02-03, 2007, Port Elizabeth, South Africa [doi>10.1145/1292491.1292493]
• 6: Colin Chibaya , Shaun Bangay, Flock Inspired Area Coverage Using Wireless Boid-Like Sensor Agents, Proceedings of the Tenth International Conference on Computer Modeling and Simulation (uksim 2008), p.144-149, April 01-03, 2008 [doi>10.1109/UKSIM.2008.102]
• 7: Carson G. David. Statnotes: Topics in Multivariate Analysis. Retrieved on 15/08/2008 from http://www2.chass.ncsu.edu/garson/pa765/statnote.htm, 2008.
• 8: Bavaud F, Chappelier J. C, and Kohlas J. An introduction to information theory and Applications, March 2005.
• 9: David Feldman. A brief introduction to: Information theory, excess entropy and computational mechanics. College of the Atlantic, ME 04609, October 2002.
• 10: Kirsty Kitto. Modelling and generating complex emergent behaviour. PhD thesis, The School of Chemistry, Physics and Earth Sciences, The Flinders University of South Australia, June 2006.
• 11: David M. Lane. Computing Pearson's Correlation Coefficient. Retrieved on 15/08/2008 from http://davidmlane.com/hyperstat/A51911.html, 2007.
• 12: Peter Martin. Beginning research on the quantification of spatial order. In Proceedings of the SIRC 2006- The 18th Annual Colloquium of the Spatial Information Research Center, University of Otago, New Zealand, November 2006.
• 13: Jeremy Miles. Table of Critical values for Pearson correlation. Retrieved on 15/08/2008 from http://www.jeremymiles.co.uk/misc/tables/pearson.html. Santa Monica, 2008.
• 14: Crutchfield James P. and Feldman David P. Regularities unseen, randomness observed: Levels of entropy convergence, chaos, in press, 2001a. e-print, arxiv.org, cond-mat/0102181. CHAOS, in press, 2001a. E-print, arxiv.org, cond-mat/0102181., February 2001.
• 15: Feldman David P. and Crutchfield James P. Discovering noncritical organization: Statistical mechanical, information theoretic, and computational views of patterns in one-dimensional spin systems. santa fe institute working paper., April 1998.
• 16: Thomas D Schneider. Information Theory Primer with an Appendix on Logarithms. PhD thesis, National Cancer Institute, Laboratory of Experimental and Computational Biology, April 2007.
• 17: Ricard V. Solé , Octavio Miramontes, Information at the edge of chaos in fluid neural networks, Physica D, v.80 n.1-2, p.171-180, Jan. 1, 1995 [doi>10.1016/0167-2789(94)00158-M]
• 18: William M. K. Trochim. Research Methods Knowledge Base: Descriptive statistics: Correlation. Retrieved on 15/08/2008 from http://www.socialresearchmethods.net/kb/statcorr.php, 2006.
• 19: Pere-Pau Vazquez and Mateu Sbert. Perception-based illumination information measurement and light source placement. In Lecture Notes in Computer Science, Proceedings of ICCS., pages 149--157, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Keywords:
correlation, distance, emergence, entropy, information, shortest path, significance level, similarity, uncertainty