Complexity Explorer Santa Few Institute

The Inaugural Complexity Challenge: from UAVs to checkers and back

08 Nov 2017

The Complexity Challenges offer an unparalleled opportunity for individuals wanting to flex their complexity knowledge muscles experience the vertigo and thrill of rigorous, creative and collaborative problem solving that is at the core of the best research emerging from the Santa Fe Institute.  These Challenges will be offered every year and will be open to any qualified person that wants to take part.  The solutions created by these individuals have the potential to directly impact research being carried out on those topics, as they will be grounded in real, current issues at the forefront of science today.

The first ever Complexity Challenge featured a diverse cohort of 50 individuals from Santa Fe Institute education programs like Complex System Summer Schools, Short Courses, Research Experiences for Undergraduates, as well as students of Complexity Explorer who have completed multiple courses on our site.  

Congratulations Ellen Badgley, Mika Straka, Zhiya Zuo and Rohan Mehta!

These four individuals submitted the highest ranked solutions to our inaugural Complexity Challenge, based on peer reviews, mentor reviews, the instructor's reviews and our organizational partner's reviews.  Jump to the end to dig deeper into their solutions, read on from here to get the bigger picture of the Challenge process.

Challenges go through multiple phases, from inspiration, through abstraction, problem solving, generalizing and exposure to other solutions. 

  • InspirationHow do you design an autonomous vehicle system? How do you plan for emergence in these systems? How simple can you make these systems while maximizing their robustness? All of these questions and more troubled our partner, Matt Koehler of Mitre Corporation, as he and John Miller brainstormed what would make a good Challenge question.  
  • Abstraction:  John took the inspiration provided by Matt and stripped it of its context and biases to create a study system representing key aspects of the original question, and open enough to allow creative solutions to emerge from the pool of candidates.  Watch John explain his checkerboard abstraction here. 
  • ProcessParticipants spent one month dissecting the question, talking with each other and the mentors, and designing their solutions.  Along the way they thought about how the checkerboard problem relates to the real world, without knowing what the inspiration was.  They uploaded papers and videos explaining their solutions and then they all reviewed each other.
  • Key Insights: All the solutions were interesting and well researched.  The appearance of congestion and coupling with the checkers was a problem many participants had to work to solve.  Identifying the optimal amount of information a checker should have implied that more is not always better.  One participant looked into different computational efficiencies, which has interesting implications for how much algorithmic complexity to build into self-driving vehicles.  

 

Launch of the Complexity Challenges featured solutions

Explore the problem and the participants' solutions by watching the video playlist.  The top four submission write ups are available for you to look over as well.

  • The top 2 solution write-ups can be found here and here
  • 2 honorable mention write-ups can be found here and here

 

Top participant profiles: Rohan, Ellen, Zhiya and Mika

Why take part in the Challenge?

Mika Straka, PhD student in complex networks at IMT Lucca, Italy"I participated in the Complex Systems Summer School of the Santa Fe Institute in 2016 - and loved it. Coming from a background of theoretical physics, I enjoyed the interdisciplinary orientation of the school and the merging of methods that the SFI conveys. For my PhD, I work in the field of complex networks with main applications to economic systems. The Complexity Challenge, however, dealt with something completely different: autonomous moving objects.  It gave me the perfect occasion to relive the Santa Fe approach: take a problem, and play with it. Look at it from different angles, consider different approaches, search for parallels to other systems. And above all: have fun."

Ellen Badgley, Mitre Corporation: "I'm actually a software engineer working for the MITRE Corporation, the Complexity Network partner that helped design the inaugural Challenge.  I did this purely on my own time/resources, and specifically avoided talking to any fellow employees involved in the Challenge until after it was over.  (In fact, I had no idea that MITRE was involved in the Challenge at all until I saw the initial announcement!)  I decided to take part in the Challenge with absolutely no thought of "winning", but primarily to give myself an excuse to dive into an interesting complexity problem, explore some new tools and techniques, and help SFI refine this program further.  I participated in the SFI Complex Systems Summer School in 2016 and loved the entire experience, and am excited about SFI and its outreach in general." 

Zhiya Zuo, University of Iowa PhD candidate in information science: "SFI’s complexity summer school in 2017 gave me some understanding of complexity science so the complexity challenge was definitely a perfect way for me to try something out in this exciting field."

Rohan Mehta, Stanford graduate student in mathematical biology: "I thought it would be fun, and a good opportunity to practice thinking about a problem from scratch as opposed to building on something someone else has done."

 

What types of systems did you focus on while solving the Challenge, and how did you solve the checkerboard problem?

Rohan: "I focused on organic autonomous things (humans and other animals) instead of inorganic ones, probably due to my background.  There are several systems where humans need to get to particular spots and have to deal with other humans who also need to get to different particular spots (like in a locker room or at a convention center or at a train station)  My favorite application was from a solution that I peer-reviewed, which was autonomous robots in an Amazon warehouse.

I started out with a purely local strategy, trying to find out what the best rules were when only considering what one checker needed to do.  After getting uninspiring results, I switched to thinking about what kind of shapes are best for the checker paths to be. I tried a linear path first (checkers move as close as possible on diagonal lines to their destination), but the checkers ended up interefering with each other too much.  I then tried S/Z-shaped paths, which would potentially minimize intereference between checkers.  They worked really well, and so refining that strategy (and working around some emergent phenomena) was the rest of the work."

Zhiya: "My first guess on the original goal behind the question was pedestrian dynamics (evacuation or just human dynamics in public areas) so I started to search for related literature on this. I got inspirations from social force models but, as a data scientist instead of a physicist, I chose to make rules for building a agent based model. Briefly, each agent will either move forward or stay put, without the intention to move backwards in a sense of being “greedy”. Two measures (one for system-wise and the other for agent-wise) were introduced to quantify the efficiency."

Mika: "I think it was quite clear that the Challenge referred to autonomous vehicle systems. Nonetheless, initially I also considered treating the system from the perspective of surface growth. Surface growth dynamics are characterized by universal scaling relations across systems. It would have been interesting to see whether the configurations created by different checker types on the board could be categorized in different universality classes. However, due to the fixed size of the board and the fact that successful checkers should be removed, I discarded the idea.

Despite recent advancements in mobile robotics, drones, and self-driving cars, the topic of autonomous  vehicles has still to address a fundamental question: how can we minimize travel times while avoiding crashes and guaranteeing public safety?  My idea was to implement an agent-based toy model of the checker board described in the Complexity Challenge and to explore the properties of the system with respect to two types of "autonomous moving checkers". On the one hand, I considered a very simple checker that preferably moved in straight lines. On the other hand, I also took a more complex object into account that used a more computation-heavy shortest-path algorithm to calculate the best trajectories. Due to the independence of the checkers on the board, however, the former outperformed the latter in many cases."

Ellen"When I first saw the Challenge abstract, I thought it was a perfect situation for an agent-based model, and I chose to use one particular framework -- MASON, a Java ABM framework developed at George Mason University -- to develop said model, since I had been intending to deepen my understanding of that tool.  I did settle on autonomous vehicle systems as the most likely real-world situation at play, specifically because of the lack of communication between the "checkers".  Others include pedestrian behavior, drone routing, and the like. 

My Challenge entry involved extremely simple measures of efficiency, so I would definitely be open to branching out and exploring deeper.  I had initially intended to use an evolutionary algorithm to help develop my movement rules, but I found that exploring the basic parameters of the model I developed kept me pretty occupied and held plenty of interesting possibilities in and of itself." 

 

Do you have plans to extend the work you did for the Challenge?

Mika: "I would like to dedicate some more time to the problem and to follow through with some ideas. We will see whether I will find the time - the next Complexity Challenge is soon to start."

Rohan"Yes. I am in contact with the other people who shared their contact info, so we'll see if something comes out of that.  If not, I have a couple of ideas for extending the analysis of my particular solution that might be worth looking at."

Ellen: "I definitely would like to develop this into a more sophisticated platform, potentially even as an educational model."

Zhiya"I definitely would love to work on this further but this depends on whether I can find collaborators."

 

What advice would you give future Challenge participants?

Zhiya"Being a novice in this field, I would suggest skimming related research to get inspired and try to link some ideas with your own expertise."

Ellen"Think big, but be prepared to scale back if you have to.  4-6 weeks is not a lot of time at all, especially if you are dealing with new tools and techniques.

Don't be afraid to take a "left turn" and explore an emergent behavior that you didn't originally intend to investigate!

If you get stuck, ask on the forums, or elsewhere.  Even though submissions are individual, collaboration (especially interdisciplinary collaboration) is by far the best way to tackle hard problems.  The important part, of course, is to give credit where credit is due. 

Keep in mind that the product of the Challenge is not your model, but your writeup and video.  In other words, the most important thing is being able to articulate what you've done, clearly and concisely.  This is true in all scientific and professional communication, after all!  In particular, is there an "aha" that you want a reader/viewer, particularly someone outside your field or a non-scientific person in general, to take away from your approach?  Also, clarity and conciseness doesn't mean fancy graphics or video production values - do what you need to do to convey what you want to convey.  (I had never done any video editing before putting together my submission.)

If you're not enjoying the experience, step back, take a break, and think about how you might make it fun again, even if that's going in a completely different direction.  

Mika: "Play with it. Don't take it too seriously, have fun instead and try things out. If you have difficulties coding your solution or if your algorithm is too slow, then ask for advice. There is nothing wrong about that." 

Rohan"Don't try to be perfect, but do try to be good."


Comment on this article:

You must be logged in to comment

Comments

← Back to news stories