Considering User Experience in Crowdsourced Problem Solving

I received a lot of positive email feedback regarding yesterdays idea of using collective intelligence to address NP-Complete problems. Thanks a lot!

Firstly the problem and solution are unashamedly inspired by Luis von Ahn's research. Specifically, his notions of Games with a Purpose (pdf) and the games and services he has released along these lines: reCAPTCHA, The ESP Game, Peekaboom, and Phetch. Click them, try them, love them. Awesome ideas! This is not a big secret, as I have spammed my interest in this research many times on this blog.

What I clearly lacked from the project proposal was any consideration of user experience. This was reflected in much of my feedback (cheers): Why would the user come back? What is in it for the user? How does it help the user? How are the puzzles compelling? What motivates the user to solve your problem in a piecewise manner? So on.. This area needs work, superseding all technical work, for now.

Some user experience models that come to mind are:

• Gimmick: This was the original notion. I was caught up in the emergent effect and considered user participation based on excitement over the gimmick, and at a stretch as a single player game. In my mind I relate the gimmick model with interesting AJAX sites (one hit wonders), specifically collaborative drawing sites like The Broth, beautyandchaos, draw ball, and may others.
  
• Educational: The site could be geared towards education, demonstrating how local problem solving contributes to holistic problem solving, emergence in human-based algorithms, or specifically education regarding the TSP itself.
  
• Single Player Game: Beyond the gimmick of the project, I thought the accumulation of scores for a user may turn the "quality" or number of contributions into a competition. A hazard with this approach is that scoring could bias the resultant holistic solutions. For example, rewarding local Nearest Neighbor solutions would merely approximate the NN solution at aggregation time. A leader board based approach would be compelling enough for me to play (I think), as long as it looked cool (back to gimmick).
  
• Two Player Game: This is a more interesting approach where users are paired randomly and compete with each other with random sub-graphs. The goal may be to match solutions, compete based on time (exploit reflexive structure identification), compete against the same objective (minimising) or compete with conflicting objectives (one minimise and one maximise).
  

All interfaces could be provided and iterated to find the most compelling user experience (at least during early testing). It is clear to me that contributions must capture the powerful human capacity for pattern recognition in the identification of underlying structure. Specifically, this must be discriminated from automated nearest neighbour solutions which can be automated. I think of the human contributions as an innate mixture of heuristic and acquired knowledge (if you are familiar with ACO) that when aggregated over many local sub-problems provides an approximately optimal solution. This is the primary question to be answered by the application.

Some additional insights (thanks Craig and Cam):

• Consider an integration with Google maps, solving real TSP's is more compelling than arbitrary points on the screen. A brilliant suggestion I overlooked on the first pass.
• Consider a facebook application if for the size of the userbase if nothing else. I had a similar thought (blog widget). A winner, as long as compelling variations of the game + meaningful aggregates can be defined.
• Consider the use of the sub-tours/sub-graphs as reCAPTCHA's. I think in their native form, this may not be as straight forward because there must be a single solution that is easy for the user (NN? Globally optimal?) and which is hard for the computer to locate (not the first, but defiantly the second).
  

This last point got me thinking about transformations of the problem. My first inclination was to show random sub-problems with random rotations to capture invariant structures, although there are more powerful polynomial time transformations of the problem into related problems that could be exploited. You could also visually display local information in many different ways (terrain, etc). I need to think about this, specifically with regard to visual transformations which can exploit human pattern recognition useful to the global problem.

I didn't get into any tech today other than some brief playing with the tools and the database. I invested available time today on mocking out the data model (on paper), and thinking about user experience and collaborative games (time well invested). I'm staying with the user for now.