{"id":791,"date":"2008-02-08T08:50:50","date_gmt":"2008-02-08T08:50:50","guid":{"rendered":"http:\/\/UnhinderedByTalent.com\/Phi\/archives\/2008\/02\/08\/decentralized-distributed-systems-evolutionary-computation-and-prisoners-dilemma\/"},"modified":"2008-02-08T08:59:28","modified_gmt":"2008-02-08T08:59:28","slug":"decentralized-distributed-systems-evolutionary-computation-and-prisoners-dilemma","status":"publish","type":"post","link":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2008\/02\/08\/decentralized-distributed-systems-evolutionary-computation-and-prisoners-dilemma\/","title":{"rendered":"Decentralized, distributed systems, evolutionary computation, and prisoner&#8217;s dilemma"},"content":{"rendered":"<p><a href=\"http:\/\/www.flickr.com\/photos\/nicmcphee\/31627560\/\" title=\"Farming up close and personal by Unhindered by Talent, on Flickr\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/i0.wp.com\/farm1.static.flickr.com\/21\/31627560_bb4f4a3dc8_m.jpg?resize=190%2C240\" width=\"190\" height=\"240\" alt=\"Farming up close and personal\" align='right' vspace='10' hspace='10' data-recalc-dims=\"1\" \/><\/a><\/p>\n<p class=\"p1\">Chris posted some cool questions on <a href=\"http:\/\/unhinderedbytalent.com\/Phi\/archives\/2008\/01\/11\/i-think-my-head-is-full-of-ants\/#comment-32290\">my earlier post<\/a> about decentralized behavior in social insects:<\/p>\n<p class=\"p2\"><\/p>\n<blockquote><p>\nso what kinds of things do computer scientists do w\/this idea? is sort of what evolutionary computing is about? i picked up the evolution of cooperation recently (tit for tat wins prisoner\u2019s dilemma) you must be familiar w\/this, yes?\u201d<\/p><\/blockquote>\n<p class=\"p2\"><\/p>\n<p class=\"p1\">There\u2019s really three different (but related) ideas in this question:<\/p>\n<ul>\n<li>Decentralized and emergent behavior<\/li>\n<li>Evolutionary computation<\/li>\n<li>Game theory and cooperation<\/li>\n<\/ul>\n<p class=\"p4\">I\u2019ll take them one at a time, with more on the first of the three, at least for now.<\/p>\n<p><!--more--><\/p>\n<p class=\"p4\"><b>Decentralized and emergent behavior<\/b><\/p>\n<p class=\"p4\">People in computing are still trying to figure out how to best use the amazing things that we\u2019re learning about critters like social insects. Probably the most promising application area is where you need flexible autonomous agents that don\u2019t require some sort of central control.<\/p>\n<p class=\"p4\">One of the easiest examples would be robot exploration of a distant planet like Mars. Communication between here and there is slow enough that if you rely on control from Earth (as we currently do), things move <i>very<\/i> slowly. If, on the other hand, you \u201clet them loose\u201d there is a real risk that they\u2019ll fall off a cliff or get stuck on a rock or whatever, and the process of replacing them is a lot slower (and more expensive) than the process of controlling them from here. An alternative, though, is to send a lot (dozens, maybe hundreds) of small and (relatively) cheap robots that work independently. In this scenario you <i>expect<\/i> to lose some, but count on enough surviving that you still accomplish the primary task. So instead of sending the great, lumbering <i>Lost in space<\/i> robot, you send a swarm of robotic ants, planning to lose a some (like worker ants) but doing great things in aggregate.<\/p>\n<p class=\"p4\">And this isn\u2019t just a science fiction exercise. There are very real military applications of these ideas; imagine a hoard of reconnaissance robots, for example, in a battle theatre. You have to presume you\u2019ll lose some of them, and you can\u2019t have them depend on a single central control as that would present a serious weak point. There are also people exploring applications of these ideas for tasks like cleanup in extremely hazardous environment such as Chernobyl. Out on the edges of the spectrum, you have people proposing swarms of micro- or nano-devices, none of which are very smart, but which can in aggregate accomplish significant tasks.<\/p>\n<p class=\"p4\">One vision I\u2019ve daydreamed about for several years, for example, would be replacing the massive combine harvester style of agriculture with a swarm of little \u201cagribots\u201d. These could handle things like planting, weeding, pest control, and potentially even harvesting without the need for huge expensive machines or grinding physical labor. One thing this could allow is the use of highly mixed plantings instead of the massive, fragile mono-cultures that define most of modern agriculture. Highly mixed plantings are essentially impossible in the current state of industrial agriculture, which favors vast fields of uniform crops, but were very common in pre-industrial agriculture.<\/p>\n<p class=\"p4\">At some level there\u2019s a serious conflict between these approaches to problem solving and traditional computing. Most computer science is built on notions of precision and exact reproducibility. When you sort a list, for example, you want to <i>sort<\/i> a list in an exact and predictable way. It\u2019s hard to predict with any precision the behavior of distributed systems with no centralized control. You can say things about their general behavior (they \u201ctend\u201d to do this or that), but it\u2019s hard to perform any sort of exact analysis. This has made it hard to sell these ideas in certain quarters, especially if people want or need some level of precise understanding.<\/p>\n<p class=\"p4\"><b>Evolutionary computation<\/b><\/p>\n<p class=\"p4\">These kinds of decentralized, distributed systems are not inherently connected to the area of evolutionary computation (EC), although EC is often used to to aid in the programming them.<\/p>\n<p class=\"p4\">In EC you evolve an (often approximate) solution to a problem. You typically start with a randomly generated collection of potential solutions to a problem. Some of these are better solutions than others, so you pull out the best and mutate and\/or recombine them in some way to generate a new population. Again, some of those are better than others, so you use the better ones to make a new population. This process is repeated until either a reasonable solution is found, or you get bored and try again.<\/p>\n<p class=\"p4\">This can work very well in certain circumstances, usually where (a) you\u2019re OK with an approximate solution (evolution is best at producing solutions that are \u201cgood enough\u201d rather than \u201cperfect\u201d), (b) you\u2019re working in a domain that we don\u2019t understand well (there\u2019s no point in goofing around with evolving approximate solutions if we have tools that provide exact solutions), and (c) you do have a good way of judging the quality of solutions (without which you can\u2019t decide who are the \u201cwinners\u201d in the evolutionary process).<\/p>\n<p class=\"p4\">EC is used in a whole host of settings, some of which are very cool. (There was a great example a few years ago of evolving a satellite antenna which I could say some more about if folks are interested.) Writing programs to control highly distributed, decentralized systems remains a very challenging problem, but we can often measure how well a swarm of agents solves a problem even if we don\u2019t really understand how they accomplish the task. Consequently EC is often at least one of the tools that is considered when developing distributed, decentralized multi-agent systems.<\/p>\n<p class=\"p4\"><b>Game theory and cooperation<\/b><\/p>\n<p class=\"p4\">The prisoner\u2019s dilemma problem has long since been a favorite of mine, and I could blather on about it at great length. Sticking to the general theme here, however, it\u2019s a nice example of a problem where the agents involved have to make decisions without being able to coordinate or communicate beforehand.<\/p>\n<p class=\"p4\">I&#8217;m definitely aware of (and highly recommend) Axelrod&#8217;s <em>Evolution of cooperation<\/em> and his other work on the prisoner\u2019s dilemma problem; it\u2019s easy to over-interpret some of the ideas in his book, but there is still much to be said there about cooperation, trust, and responding to threats. Hofstadter also has an nice discussion of this and a host of related problems in several chapters of <i>Metamagical themas<\/i>.<\/p>\n<p class=\"p4\">The evolution of cooperation has long been (and remains) a central question in biology as well as in evolutionary computation.  Prisoner&#8217;s dilemma has, as a result, been a subject of considerable study in the EC community.  It (along with numerous other examples from game theory) has also formed the basis of numerous EC studies in areas such economics and market studies.<\/p>\n<p>Thanks to Chris for the excellent questions!<\/p>\n\n\t<div class=\"st-post-tags \">\n\tTags: <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/computing\/\" title=\"Computing\">Computing<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/cooperation\/\" title=\"cooperation\">cooperation<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/distributed-systems\/\" title=\"distributed systems\">distributed systems<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/emergent-behavior\/\" title=\"emergent behavior\">emergent behavior<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/evolution\/\" title=\"evolution\">evolution<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/evolutionary-computation\/\" title=\"evolutionary computation\">evolutionary computation<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/insects\/\" title=\"insects\">insects<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/prisoners-dilemma\/\" title=\"prisoner&#039;s dilemma\">prisoner&#039;s dilemma<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/programming\/\" title=\"programming\">programming<\/a>, <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/tag\/science\/\" title=\"Science\">Science<\/a><br \/><\/div>\n\n\n\t<h4>Related posts<\/h4>\n\t<ul class=\"st-related-posts\">\n\t<li><a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2010\/07\/12\/massive-road-trip-days-7-11\/\" title=\"Massive road trip, days 7-11 (12 Jul 10)\">Massive road trip, days 7-11<\/a> (0)<\/li>\n\t<li><a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2008\/01\/11\/i-think-my-head-is-full-of-ants\/\" title=\"I think my head is full of ants (11 Jan 08)\">I think my head is full of ants<\/a> (2)<\/li>\n<\/ul>\n\n","protected":false},"excerpt":{"rendered":"<p>Chris posted some cool questions on my earlier post about decentralized behavior in social insects: so what kinds of things do computer scientists do w\/this idea? is sort of what evolutionary computing is about? i picked up the evolution of cooperation recently (tit for tat wins prisoner\u2019s dilemma) you must be familiar w\/this, yes?\u201d There\u2019s &hellip; <a href=\"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2008\/02\/08\/decentralized-distributed-systems-evolutionary-computation-and-prisoners-dilemma\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Decentralized, distributed systems, evolutionary computation, and prisoner&#8217;s dilemma&#8221;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_newsletter_tier_id":0},"categories":[4,12,15],"tags":[859,245,243,208,66,228,79,244,82,866],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p90sy-cL","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"jetpack-related-posts":[{"id":807,"url":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2008\/02\/28\/jocp-at-revision-400\/","url_meta":{"origin":791,"position":0},"title":"JOCP!  At revision 400!","author":"Nic McPhee","date":"28 Feb 08","format":false,"excerpt":"It's pretty cool when you update your repository and see At revision 400 We just hit that on the genetic programming book that Riccardo and Bill and I are working on; we're currently averaging close to 10 commits a day here in the final stages. We hope to wrap it\u2026","rel":"","context":"In &quot;Books&quot;","block_context":{"text":"Books","link":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/category\/writing\/books\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1337,"url":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2010\/07\/29\/just-2-days-left-genetic-programming-and-evolvable-machines-anniversary-issue-available-for-free\/","url_meta":{"origin":791,"position":1},"title":"Just 2 days left: Genetic Programming and Evolvable Machines anniversary issue available for free!","author":"Nic McPhee","date":"29 Jul 10","format":false,"excerpt":"The Springer journal Genetic Programming and Evolvable Machines is celebrating its first 10 years with a special anniversary issue of articles reviewing the state of the field and considering some of its possible futures. For the month of July the entire issue is available for free!","rel":"","context":"In &quot;Computing&quot;","block_context":{"text":"Computing","link":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/category\/computing\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":811,"url":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2008\/03\/06\/not-quite-a-wave\/","url_meta":{"origin":791,"position":2},"title":"Not quite a wave","author":"Nic McPhee","date":"6 Mar 08","format":false,"excerpt":"Sometimes you're just minding your own business, trying to get a little science done, and a little art pops out at you all unexpected. What?!? You want to know where this comes from? All is revealed beneath the fold... The dotted line is, not surprisingly, the sine function plotted from\u2026","rel":"","context":"In &quot;Art&quot;","block_context":{"text":"Art","link":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/category\/art\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1265,"url":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2010\/05\/10\/im-published-in-cacm-but-not-in-the-way-one-might-have-thought\/","url_meta":{"origin":791,"position":3},"title":"I&#8217;m published in CACM! (But not in the way one might have thought)","author":"Nic McPhee","date":"10 May 10","format":false,"excerpt":"The May, 2010, issue of the Communications of the ACM (CACM - the flagship magazine of the ACM) features a photograph of UMM CSci alum Tyler Hutchison presenting research work done with Andy Korth and Nic McPhee at MICS 2007. The article is \"Student and Faculty Attitudes and Beliefs About\u2026","rel":"","context":"In &quot;Art&quot;","block_context":{"text":"Art","link":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/category\/art\/"},"img":{"alt_text":"CACM page spread featuring UMM CSci alum Tyler Hutchison at MICS","src":"https:\/\/i0.wp.com\/farm5.static.flickr.com\/4022\/4594073817_bdb17727b0.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":356,"url":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2006\/07\/09\/greetings-from-seattle\/","url_meta":{"origin":791,"position":4},"title":"Greetings from Seattle!","author":"Nic McPhee","date":"9 Jul 06","format":false,"excerpt":"I'm happily ensconced here in Seattle for GECCO 2006 (one of the major conferences in evolutionary computation, my primary research area), and managing to sneak in a few pictures now and then. The photograph above isn't a great one, but it shows the mighty mountain in the distance, which isn't\u2026","rel":"","context":"In &quot;Computing&quot;","block_context":{"text":"Computing","link":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/category\/computing\/"},"img":{"alt_text":"Lots o' geometry","src":"https:\/\/i0.wp.com\/static.flickr.com\/58\/185297528_499850fa23.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":781,"url":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/2008\/01\/25\/wrapping-ones-head-around-the-data\/","url_meta":{"origin":791,"position":5},"title":"Wrapping one&#8217;s head around the data","author":"Nic McPhee","date":"25 Jan 08","format":false,"excerpt":"JOCP! It's been almost five days since I've posted anything here, and I have so much backed up in the queue... There's a major conference deadline (GECCO 2008) in a few days, and I'm struggling to finish up four different (and only loosely related) papers for submission. On top of\u2026","rel":"","context":"In &quot;Computing&quot;","block_context":{"text":"Computing","link":"https:\/\/UnhinderedByTalent.com\/Phi\/archives\/category\/computing\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/posts\/791"}],"collection":[{"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/comments?post=791"}],"version-history":[{"count":0,"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/posts\/791\/revisions"}],"wp:attachment":[{"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/media?parent=791"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/categories?post=791"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/UnhinderedByTalent.com\/Phi\/wp-json\/wp\/v2\/tags?post=791"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}