Top

Natural Computing

Published in:

01-09-2012

To boldly go: an `occam`-π mission to engineer emergence

Authors: Peter H. Welch, Kurt Wallnau, Adam T. Sampson, Mark Klein

Published in: Natural Computing | Issue 3/2012

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Future systems will be too complex to design and implement explicitly. Instead, we will have to learn to engineer complex behaviours indirectly: through the discovery and application of local rules of behaviour, applied to simple process components, from which desired behaviours predictably emerge through dynamic interactions between massive numbers of instances. This paper describes a process-oriented architecture for fine-grained concurrent systems that enables experiments with such indirect engineering. Examples are presented showing the differing complex behaviours that can arise from minor (non-linear) adjustments to low-level parameters, the difficulties in suppressing the emergence of unwanted (bad) behaviour, the unexpected relationships between apparently unrelated physical phenomena (shown up by their separate emergence from the same primordial process swamp) and the ability to explore and engineer completely new physics (such as force fields) by their emergence from low-level process interactions whose mechanisms can only be imagined, but not built, at the current time.

previous article Evolutionary mechanics: new engineering principles for the emergence of flexibility in a dynamic and uncertain world

next article Programming and evolving physical self-assembling systems in three dimensions

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Photographs showing remarkably similar shapes in flocks of starlings can easily be found by searching the Internet. They cannot be included in this paper for copyright reasons, nor referenced because of the volatility of their URLs. However, links to images matching those in Fig. 8 can be found in the supporting materials for this paper (Welch et al. 2011b).

Adams D (1987) Dirk Gently’s Holistic Detective Agency. Gallery Books. See also: http://en.wikipedia.org/wiki/Duck_test

Andrews PS, Sampson AT, Bjørndalen JM, Stepney S, Timmis J, Warren DN, Welch PH (2008) Investigating patterns for the process-oriented modelling and simulation of space in complex systems. In: Bullock S, Noble J, Watson R, Bedau MA (eds) Artificial life XI: proceedings of the eleventh international conference on the simulation and synthesis of living systems, pp 17–24. MIT Press, Cambridge, MA URL http://www.cosmos-research.org/docs/alife2008-space.pdf

Andrews P, Stepney S, Winfield A (2010) Simulation as an experimental design process. EmergeNET4: engineering emergence URL http://www.cs.york.ac.uk/nature/emergeNET4/andrews.pdf. AF/ST-TR-10-01-PR

Baker L (2009) Removing roads and traffic lights speeds urban travel. Scientific American URL http://www.scientificamerican.com/article.cfm?id=removing-roads-and-traffic-lights

Ballerini M, Cabibbo N, Candelier R, Cavagna A, Cisbani E, Giardina I, Lecomte V, Orlandi A, Parisi G, Procaccini A, Viale M, Zdravkovic V (2008) Interaction ruling animal collective behavior depends on topological rather than metric distance: evidence from a field study. Proc Natl Acad Sci 105(4):1232–1237. URL http://www.pnas.org/cgi/doi/10.1073/pnas.0711437105

Barnes FRM, Welch PH (2001) Mobile data, dynamic allocation and zero aliasing: an occam experiment. In: Chalmers A, Mirmehdi M, Muller H (eds) Communicating process architectures 2001, Concurrent Systems Engineering, vol 59. WoTUG, IOS Press, Amsterdam, The Netherlands, pp 243–264. ISBN: 1-58603-202-X

Barnes FRM, Welch PH (2004) Communicating mobile processes. In: East I, Martin J, Welch P, Duce D, Green M (eds) Communicating process architectures 2004, Concurrent Systems Engineering Series, ISSN 1383-7575, vol 62, WoTUG-27. IOS Press, Amsterdam, The Netherlands, pp 201–218. ISBN: 1-58603-458-8

Barnes FRM, Welch PH, Moores J, Wood DC (2010) The KRoC home page. Programming Languages and Systems Research Group, University of Kent, http://www.cs.kent.ac.uk/projects/ofa/kroc/

Bently PJ (eds) (1999) Evolutionary design by computers. Morgan Kaufmann, San Francisco

Bjørndalen JM, Sampson AT (2008) Process-oriented collective operations. In Welch PH, Stepney S, Polack FA, Barnes FR, McEwan AA, Stiles GS, Broenink JF, Sampson AT (eds) Communicating process architectures 2008, Concurrent Systems Engineering, vol 66, WoTUG, IOS Press, Amsterdam, The Netherlands, pp 309–328. URL http://www.cosmos-research.org/docs/cpa2008-poco.pdf

Brown NCC (2008) Communicating Haskell processes: composable explicit concurrency using monads. In: Welch PH, Stepney S, Polack FA, Barnes FR, McEwan AA, Stiles GS, Broenink JF, Sampson AT (eds) Communicating process architectures 2008, Concurrent Systems Engineering, vol 66, pp 67–83. WoTUG, IOS Press, Amsterdam, The Netherlands. URL http://www.cs.kent.ac.uk/pubs/2008/2914

Brown NCC (2010a) C++CSP home page. Programming Languages and Systems Research Group, University of Kent, http://www.cs.kent.ac.uk/projects/ofa/c++csp/

Brown NCC (2010b) Communicating Haskell processes home page. Programming Languages and Systems Research Group, University of Kent, http://www.cs.kent.ac.uk/projects/ofa/chp/

Brown NCC, Welch PH (2003) An introduction to the Kent C++CSP Library. In: Broenink J, Hilderink G (eds) Communicating process architectures 2003, W o TUG-26, Concurrent Systems Engineering, ISSN 1383-7575. IOS Press, Amsterdam, The Netherlands, pp 139–156. ISBN: 1-58603-381-6

Dahm WJA (2010) Technology horizons: a vision for air force science and technology during 2010–2030, vol I. United States Air Force Chief Scientist (AF/ST). AF/ST-TR-10-01-PR

Davison A (2005) Killer game programming in Java. Chapter 22, flocking boids. O’Reilly Media Inc., USA

Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, CambridgeMATHCrossRef

Easley D, Kleinberg J (2010) Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press. URL http://www.cs.cornell.edu/home/kleinber/networks-book/

Edelman B, Ostrovsky M, Schwarz M (2005) Internet advertising and the generalized second price auction: selling billions of dollars worth of keywords. Working paper 11765, National Bureau of Economic Research. URL http://www.nber.org/papers/w11765

Hemelrijk CK, Hildenbrandt H (2008) Self-organized shape and frontal density of fish schools. Ethology 114(3):245–254. URL http://onlinelibrary.wiley.com/doi/10.1111/j.1439-0310.2007.01459.x/abstract

Hoare CAR (1974) Monitors: an operating system structuring concept. Commun ACM 17(10):549–557MATHCrossRef

Hoare CAR (1978) Communicating sequential processes. CACM 21(8):666–677MATH

Hoare CAR (1985) Communicating sequential processes. Prentice-Hall, Upper Saddle RiverMATH

Jones RE, Barnes FRM (2010) MirrorGC: garbage collection for multicore systems. URL http://www.cs.kent.ac.uk/projects/gc/mirrorgc/. EPSRC EP/H026975/1

Klein M, Moreno GA, Parkes DC, Plakosh D, Seuken S, Wallnau K (2008) Handling interdependent values in an auction mechanism for bandwidth allocation in tactical data networks. In: Proceedings of the 3rd international workshop on economics of networked systems, NetEcon ’08. ACM, New York, NY, USA, pp 73–78. URL http://doi.acm.org/10.1145/1403027.1403044

Lorek H, Informatik F, White M (1993) Parallel bird flocking simulation. Citeseer: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.8430

Martin J, Welch P (1996) A design strategy for deadlock-free concurrent systems. Transput Commun 3(4):215–232

Milner R (1999) Communicating and mobile systems: the π-calculus. Cambridge University Press, Cambridge. ISBN-10: 0521658691, ISBN-13: 9780521658690

Polack FA, Andrews PS, Sampson AT (2009) The engineering of concurrent simulations of complex systems. In: 2009 IEEE congress on evolutionary computation (CEC 2009). IEEE Press, pp 217–224

Reynolds CW (1987) Flocks, herds, and schools: a distributed behavioral model. Comput Graph 21(4):25–34. See also: http://www.red3d.com/cwr/boids/

Ritson CG, Welch PH (2010) A process-oriented architecture for complex system modelling. Concurr Comput Pract Exp 22:965–980. doi:10.1002/cpe.1433. URL http://www.cs.kent.ac.uk/pubs/2010/3066

Ritson CG, Sampson AT, Barnes FRM (2009) Multicore scheduling for lightweight communicating processes. In: Field J, Vasconcelos VT (eds) Coordination models and languages, COORDINATION 2009, Lisboa, Portugal, June 9–12, 2009. Proceedings, Lecture Notes in Computer Science, vol 5521. Springer, pp 163–183 URL http://www.cs.kent.ac.uk/pubs/2009/2928

Roscoe A (1997) The theory and practice of concurrency. Prentice Hall, Upper Saddle River

Roscoe A (2010) Understanding concurrent systems. Springer, BerlinMATH

Rosenschein JS, Zlotkin G (1994) Rules of encounter: designing conventions for automated negotiation among computers. MIT Press, Cambridge

Roughgarden T (2010) Algorithmic game theory. Commun ACM 53(7):78–86. doi:10.1145/1785414.1785439 CrossRef

Sampson AT (2010) Process-oriented patterns for concurrent software engineering. Ph.D. thesis, University of Kent. URL http://offog.org/publications/ats-thesis.pdf

Sampson AT, Bjørndalen JM, Andrews PS (2009) Birds on the wall: distributing a process-oriented simulation. In: 2009 IEEE congress on evolutionary computation (CEC 2009). IEEE Press, pp 225–231. URL http://www.cosmos-research.org/docs/cec2009-wall.pdf

Sampson AT, Ritson CG, Jadud MC, Barnes FRM, Welch PH (2010a) occam-π home page. Programming Languages and Systems Research Group, University of Kent, http://occam-pi.org/

Sampson AT, Welch PH, Bjørndalen JM, Andrews PS (2010b) CoSMoS occoids videos. URL http://www.cosmos-research.org/demos/occoids/

Sampson AT, Ritson CG, Barnes FRM, Welch PH (2011) occam-π download and install page. Programming Languages and Systems Research Group, University of Kent, http://projects.cs.kent.ac.uk/projects/kroc/trac/wiki/Installation

Sauter JA, Matthews R, Van Dyke Parunak H, Brueckner SA (2005) Performance of digital pheromones for swarming vehicle control. In: Proceedings of the fourth international joint conference on autonomous agents and multiagent systems, AAMAS ’05, ACM, New York, NY, USA, pp 903–910. URL http://doi.acm.org/10.1145/1082473.1082610

Sayama H (2011) Seeking open-ended evolution in swarm chemistry. In: IEEE symposium on artificial life (ALIFE) 2011. IEEE Press, pp 186–193. ISBN: 978-1-61284-062-8

Schneider S (1999) Concurrent and real-time systems—the CSP approach. Wiley, UK. ISBN: 0-471-62373-3

Schweigler M (2006) A unified model for inter- and intra-processor concurrency. Ph.D. thesis, Computing Laboratory, University of Kent, Canterbury, UK, Canterbury, Kent, CT2 7NF, United Kingdom. URL http://www.cs.kent.ac.uk/pubs/2006/2429

Smith A (1904) An inquiry into the nature and causes of the wealth of nations, 5 edn. Methuen and Co., Ltd., London. First published: 1776

Stepney S, Welch PH, Polack F, Timmis J, Barnes FRM, Tyrrell A (2010) CoSMoS home page. URL http://www.cosmos-research.org/cosmos/. EPSRC EP/E053505/1 and EP/E049419/1

Stonedahl F, Wilensky U (2010) Finding forms of flocking: evolutionary search in ABM parameter-spaces. In: Proceedings of the MABS workshop at the ninth international conference on autonomous agents and multi-agent systems, Lecture Notes of Artificial Intelligence (LNCS/LNAI). Springer

Turing AM (1950) Computing machinery and intelligence. Mind, New Series 59(236):433–460. URL http://www.jstor.org/stable/2251299

Valiant L (1990) A bridging model for parallel computation. Commun ACM 33(8):103–111

Welch PH (2011) An occam-π quick reference guide. Programming Languages and Systems Research Group, University of Kent, http://www.cs.kent.ac.uk/research/groups/plas/wiki/OccamPiReference/

Welch PH, Barnes FRM (2005a) Communicating mobile processes: introducing occam-π. In: Abdallah A, Jones C, Sanders J (eds) 25 years of CSP, Lecture Notes in Computer Science, vol 3525. Springer, Berlin, pp 175–210

Welch PH, Barnes FRM (2005b) Mobile barriers for occam-π: semantics, implementation and application. In: Broenink J, Roebbers H, Sunter J, Welch P, Wood D (eds) Communicating process architectures 2005, Concurrent Systems Engineering Series, vol 63, WoTUG-28. IOS Press, Amsterdam, The Netherlands, pp 289–316. ISBN:1-58603-561-4

Welch PH, Barnes FRM (2008) A CSP model for mobile channels. In: Communicating process architectures 2008, Concurrent Systems Engineering Series, vol 66, WoTUG-31. IOS Press, Amsterdam, The Netherlands, pp 17–33. ISBN:978-1-58603-907-3

Welch PH, Brown NCC (2011) The JCSP (CSP for Java) home page. http://www.cs.kent.ac.uk/projects/ofa/jcsp/

Welch PH, Pedersen JB (2010) Santa claus: formal analysis of a process-oriented solution. ACM Trans Program Lang Syst 32(4):14:1–14:37. URL http://doi.acm.org/10.1145/1734206.1734211

Welch PH, Brown NCC, Moores J, Chalmers K, Sputh BHC (2007) Integrating and extending JCSP. In: McEwan AA, Schneider S, Ifill W, Welch P (eds) Communicating process architectures 2007, Concurrent Systems Engineering Series, vol 65. IOS Press, Amsterdam, The Netherlands, pp 349–370. ISBN:978-1-58603-767-3

Welch PH, Brown NCC, Moores J, Chalmers K, Sputh BHC (2010) Alting barriers: synchronisation with choice in Java using CSP. Concurr Comput Pract Exp 22:1049–1062

Welch PH, Pedersen JB, Barnes FRM, Ritson CG, Brown NC (2011a) Adding Formal Verification to occam-π. In: Communicating process architectures 2011, Concurrent Systems Engineering Series, vol 68, WoTUG-33. IOS Press, Amsterdam, The Netherlands, pp 379–379. URL http://www.wotug.org/papers/CPA-2011/Welch11/Welch11-slides.pdf. ISBN: 978-1-60750-773-4

Welch PH, Sampson AT, Wood DC (2011b) “To Boldly Go: an occam-π mission to engineer emergence”—supplementary materials. Programming Languages and Systems Research Group, University of Kent, http://projects.cs.kent.ac.uk/projects/naco-boldly/

Werfel J, Bar-Yam Y, Rus D, Nagpal R (2006) Distributed construction by mobile robots with enhanced building blocks. In: International conference on robotics and automation. IEEE Press

Wikipedia: DARPA Grand Challenge (2010) URL http://en.wikipedia.org/wiki/DARPA_Grand_Challenge

Yang Y, Souissi S, Défago X, Takizawa M (2011) Fault-tolerant flocking for a group of autonomous mobile robots. J Syst Softw 84(1):29–36CrossRef

Title: To boldly go: an occam-π mission to engineer emergence
Authors: Peter H. Welch
Kurt Wallnau
Adam T. Sampson
Mark Klein
Publication date: 01-09-2012
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 3/2012
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-012-9304-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2012

Evolutionary mechanics: new engineering principles for the emergence of flexibility in a dynamic and uncertain world

Parallel predator–prey interaction for evolutionary multi-objective optimization

The Gestalt heuristic: emerging abstraction to improve combinatorial search

Degeneracy and networked buffering: principles for supporting emergent evolvability in agile manufacturing systems

Comparing simulation algorithms for multienvironment probabilistic P systems over a standard virtual ecosystem

Designing a new software tool for Digital Imagery based on P systems

Premium Partner