A Human TSP Solver in Rails, One Month On

Well, it has been about a month since I proposed the idea for a web-based human TSP solver application, and I thought I would reflect a little.

• Week1: I spent the first week discussing the idea with friends and colleagues both locally in person and remotely (email and IM). I proposed the idea, considered user experience, and chose ruby on rails in which to develop. I also run some preliminary experiments (in OAT) that suggested aggregating large numbers of partial solutions using a heuristic may produce a final result close to a holistic solution with a heuristic (ideas was feasible).
  
• Week2: The second week was spent learning ruby on rails and refining the premise for the application. Three technical reports were written: the first statistically highlighting the benefit of spatial-based sub-problems over random sub-problems, the second statistically highlighting the benefit of a nearest neighbor heuristic as a viable approximate human solver over random and probabilistic (back up the first report), and the third qualitatively assessed the visualisation of solutions to spatial sub-problem in aggregate. A presentation of the premise and these findings was made to my research group, resulting in a beneficial discussion, and suggestions of additional contribution mechanism (like a maze game).
  
• Week3: The core development occurred in the third week, where a complete database schema and application schema were completed, a viable contribution mechanism devised (Java applet), and the site as whole was styled. The first version of the site was deployed and launched on HostingRails and made available to semi-private alpha testing on Friday the 16th of May 2008.
  
• Week4: The last week has involved monitoring the server logs, setting up source control, bug tracker, forum, and furiously adding features based on user feedback. The core user feedback centered around the complexity of the home page, the lack of instructions, and usability issues with the contribution applet. The end of the forth week saw the release of an update that included these changes, and the promotion of the status of the application to perpetual beta.
  

I am happy with the state of the application and my acquired rails knowledge at the end of this month. The majority of the originally envisaged features were realised, which is good given the general low complexity of the application. I spent a majority of the overall time discussing the idea and doing basic research (doing homework). I spent the majority of the development time on user interface tweaking, a task I find tedious given preference for more technical problem solving. The mix was good, although I would have liked the reports as blog posts instead of word documents, I suspect they will stay locked up forever now (lower overall quality and interestingness - imagine that).

Regarding contributions, I left the door open (some what) to allow users to define what might be useful to the holistic solution. Regarding holistic solutions, I chose not to explicitly construct a tour from the crowdsourced data, and instead left it at an XML feed of contributions and a slick visualisation - again leaving it to the users to interpret the results. This second choice was made all the more easier given that the majority of the solutions I loaded into the database from TSPLIB already had known optimal solutions, which I chose to visualise in the application.

I spent the last weekend reading up on related cognitive and computational psychology related to how and why humans are so good at solving small TSP instances, highlighting the convex hull hypothesis. I have since contacted a number of researchers in the field to gauge their thoughts regarding the premise and future for the application.

I had fun climbing into rails. I lived in the API, got most of the answers I needed from Google searches, and watched railscasts when I felt like procrastinating. Next time (say learning django or something), I would spend more time reading forums rather than tutorials, and abstract more functionality into the base language to make development and testing easier.

There is plenty of room for additional features in the app, especially alternative contribution mechanisms (games!). There is also a lot of room for application optimisation (queries and caching), if and when it becomes popular or useful. In the short-term I am going to leave the application alone, at least for a week (both development and production) while I have a play with Heroku.