Connect The Dots: A Human-Based TSP Solver

Today was a good day because I printed my thesis for examination! The integration of non-contiguous colour pages was a total pain in the ass (x3 copies of the dissertation!). Not long now before it gets sent out and assessed (torn apart?) by my peers. Crazy times...

I managed to find some time to get stuck into the design for the human-based TSP solver project (my rails project is called solver for now). The first iteration of the project will be involve a gimmick/"single player game" user experience. The motivation for the user will be to maximise a user ranking score whilst being initially drawn to the gimmick of the application. Follow-up iterations will consider some of the other proposed user experiences (such as real-time competition) as well as those not yet considered (thought up).

The so-called game involves unlimited repetitions of "connecting the dots" on small (5-10 nodes) user problems. Each user problem represents a sub-portion of a broader TSP, and the straight line through the nodes (or sub-tour) will contribute towards a holistic "collectively intelligent" solution. The specifics of the ranking equation have not been tied down as of yet, although will likely involve an aggregation of contributions across problem instances in the context of the globally optimal solution (magnitude/quality trade-off with regard to effort).

We are having a research meeting next week and I elected to present. I'm going to discuss this problem and tender suggestions for contribution aggregation schemes as well as presentation methods from my research group (complex intelligent systems lab).

The data model (schema) is simple enough. Tables for problems, problem parts, problem instances, user contributions and users. The accumulation of contributions is compressed at this time. My brain is full of nice batch update approaches using message queues and I'm finding it hard to suppress my inner architect in order to "just hack". Ideally, I'd like to store distinct contributions, although the compression approach is the way forward for now.

The screen mock-ups (pen and paper) are rudimentary although block out the core functionality. The principle screen is the presentation of the sub-problem toward capturing user contributions. The current problem instance is summarised as well as the scope of holistic contributions received for the instance thus far (users, contributions, scores, human cycles? etc.). Contributions may be captured from drive-by users (anonymous) or by those users logged in (like reddit and karma). Additional principle screens include the holistic summary of the problem instance, the user leaderboard, past problem instances with outcomes, and user details that also summaries their contributions to date (all public and RESTful).

I got my hands dirty, scaffolding much of the application, seeding the database, and reading up on rails and the new 2.0 features in particular. Firstly, most tutorials out there on rails suck, too much hello-world CRUD, not enough departure into complexity. An overview of basic rails gotchas from Shash7 was useful, as was a two-part tutorial on rails 2.0 features called Rolling with rails 2.0 (part1 and part2). I took some time and came to grips with the naming conventions so that everything plays nicely together. I climbed into ActiveRecord, fixed some plural problems, came to terms with associations and foreign keys in the model (good solid example), and investigated best practices regarding seeding the database.

I'm enjoying rails at the moment, it reminds me a lot of hacking early releases struts although with a lot more scripts and hard coded conventions. "Learning while doing" is fine while primitively architecting, although I expect there to be a crunch when I need to actually put some functionality in the application (expect lots of ruby based rants in the future).

I intend to invest a lot more time into the the user experience and psychology/presentation concerns of the subproblems after the first iteration. This last comment feels like one of those things for which time is never alloted, lucky I captured the thoughts and comments in previous posts (accountability!?). I may push the application out to the web (hosting?) late next week to start getting feedback from a private user pool.