Resume / CV

Colin McMillen

Research Interests:

In general, my research interests include the application of artificial intelligence or machine learning techniques to improve the performance of real-world systems.

For my doctoral thesis research, I investigated how teams of agents or robots can act near-optimally in timed, zero-sum games. In these domains, teams need to act in order to maximize the probability of winning, not necessarily to maximize their score. The general idea is that a team which is losing should act more aggressively to try to even the score, and a team which is winning should act more defensively to try to preserve their lead. I present algorithms which compute optimal policies for these timed domains, using Markov and semi-Markov models (MDPs and SMDPs). I also analyze how a team should change strategy in response to an opponent whose behavior is initially unknown but slowly reveals itself during execution. My thesis work has been applied to three challenging domains: the RoboCup robot soccer competition, a simulated Capture the Flag domain, and book digitization.

Education:

August 2003 -- May 2009: Carnegie Mellon University

Ph.D. in Computer Science
Dissertation title: Thresholded-Rewards Decision Problems: Acting Effectively in Timed Domains
Advisor: Prof. Manuela Veloso
GPA: 4.0/4.0

September 1999 -- May 2003: University of Minnesota, Twin Cities

B.S. in Computer Science
Graduated summa cum laude
GPA: 3.9/4.0

Work Experience:

June 2007 -- present: reCAPTCHA, Inc. (Pittsburgh, Pennsylvania)
Co-Founder; Software Engineer
Reference: Prof. Luis von Ahn

As one of the co-founders of reCAPTCHA Inc., I have worked on nearly all aspects of the reCAPTCHA system. However, my main emphasis has been the development of the back-end "CAPTCHA pipeline," which includes running OCR software on scanned documents, creating CAPTCHAs to help digitize these documents, distributing these CAPTCHAs to the front-end servers, and using probabilistic language models to analyze the OCR guesses and human answers to produce high-quality digitized output.

June 2005 -- October 2005: Sony Corporation (Tokyo, Japan)

Intern, Intelligent Systems Research Laboratory
References: Dr. Steffen Gutmann, Dr. Masahiro Fujita

While interning at Sony in Tokyo, I worked on the Sony QRIO humanoid robot. I developed a multi-robot, topological, simultaneous localization and mapping (SLAM) algorithm. This algorithm allows multiple QRIO robots to explore and map an unknown area. The robots do not need prior knowledge of teammates' positions. Instead, each robot maintains an independent map; these maps are merged together when one teammate visually recognizes another. This work was one of the first multi-robot research projects for the Sony QRIO robot. This work is patent pending (Japanese patent application #2005-349630).

August 1998 -- July 2003: Trade Cycles Creative Services (Plymouth, Minnesota)

Web developer
Reference: Jon Zydenbos

Programming, design, and database administration for several local business web sites, mostly related to automobile sales, warranties, and insurance policies.

Research Experience:

Robot Soccer (August 2003 -- present):

References: Prof. Manuela Veloso, Dr. Paul E. Rybski

I am currently doing research as a member of Carnegie Mellon University's robot soccer lab. Our team (CMDash) competes in the RoboCup Four-Legged League; in this league, teams of five Sony AIBO ERS-7 robots compete in twenty-minute games of soccer. My research has focused primarily on the development of team-level strategy, tactics, and behaviors, including team positioning, role assignment, shared world state, and passing. I have also written lower-level networking code, embedded a Python interpreter in the lower-level C++ behavior architecture (for the rapid development of behaviors), and developed a simulation framework which our team has used heavily for the development and testing of single-robot and multi-robot behaviors. I have also worked on single-robot behaviors such as the goalie and attacker.

Distributed Robotics (May 2001 -- July 2003):

Reference: Prof. Nikolaos Papanikolopoulos

I worked on improvements to the software architecture used by a group of miniature mobile robots known as the Scouts. The Scouts are a team of very small, cylindrical robots—approximately 11 cm in length and 4 cm in diameter. The Scouts are therefore very limited in processing capability, and rely on communication with more powerful robots or workstations in order to perform autonomous behaviors. My work with the Scouts included the development of a component that schedules access to limited resources such as robots, video and radio frequencies, framegrabbers, and so on. Additional work included designing and implementing an API for controlling the hardware of a new robotic platform (the MegaScout).

Trading Agent Competition (January 2003 -- July 2003):

Reference: Prof. Maria Gini

I worked on an agent for the supply-chain management game of the 2003 Trading Agent Competition. My undergraduate honors thesis provided an extensive analysis of the game, including proofs of theoretical results, metrics by which the performance of agents could be measured, and suggestions of strategies that may be of use in the implementation of sophisticated TAC SCM agents. I worked on the production and delivery aspects of an agent that competed in the 2003 competition. This agent advanced to the semi-final round.

Intelligent Transportation Systems (January 2003 -- July 2003):

Reference: Prof. Nikolaos Papanikolopoulos

I worked on an intelligent transportation systems project sponsored by the Minnesota Department of Transportation. The main goal of our research was to develop a collision warning system for intersections. Detection and tracking of moving vehicles is obtained through computer vision; detection of potential collisions utilizes techniques from the field of computational geometry. I performed preliminary work on integrating data from multiple cameras into this system.

Publications:

I am the author of four journal articles and fourteen conference papers (one best-paper award).

Journal Articles

reCAPTCHA: Human-Based Character Recognition via Web Security Measures.
Luis von Ahn, Benjamin Maurer, Colin McMillen, David Abraham, and Manuel Blum.
Science, 12 September 2008: 1465-1468.

A Team of Humanoid Game Commentators.
Manuela Veloso, Nicholas Armstrong-Crews, Sonia Chernova, Elisabeth Crawford, Colin McMillen, Maayan Roth, and Douglas Vail.
International Journal of Humanoid Robotics, 2008.

Resource Scheduling and Load Balancing in Distributed Robotic Control Systems.
Colin McMillen, Kristen Stubbs, Paul E. Rybski, Sascha A. Stoeter, Maria Gini, and Nikolaos Papanikolopoulos.
Robotics and Autonomous Systems, 2003.

A Robot Team for Surveillance Tasks: Design and Architecture.
Sascha A. Stoeter, Paul E. Rybski, Kristen N. Stubbs, Colin McMillen, Maria Gini, Dean F. Hougen, and Nikolaos Papanikolopoulos.
Robotics and Autonomous Systems, August 2002.

Refereed Conference Papers

Analysis of Multi-Robot Play Effectiveness and of Distributed Incidental Play Recognition.
Colin McMillen and Manuela Veloso.
Proceedings of Distributed Autonomous Robotic Systems (DARS 2008), November 2008.

Unknown Rewards in Finite-Horizon Domains.
Colin McMillen and Manuela Veloso.
Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI-08), July 2008.

Thresholded Rewards: Acting Optimally in Timed, Zero-Sum Games.
Colin McMillen and Manuela Veloso.
Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI-07), July 2007.
AAAI-07 Outstanding Paper Award

A Team of Humanoid Game Commentators.
Manuela Veloso, Nicholas Armstrong-Crews, Sonia Chernova, Elisabeth Crawford, Colin McMillen, Maayan Roth, and Douglas Vail.
Proceedings of the IEEE-RAS International Conference on Humanoid Robots (Humanoids'06), Genova, Italy, December 2006.

Distributed, Play-Based Role Assignment for Robot Teams in Dynamic Environments.
Colin McMillen and Manuela Veloso.
Proceedings of DARS 2006, Minneapolis, MN, July 2006.

Distributed, Play-Based Coordination for Robot Teams in Dynamic Environments.
Colin McMillen and Manuela Veloso.
Proceedings of the RoboCup International Symposium, Bremen, Germany, June 2006.

Levels of Multi-Robot Coordination for Dynamic Environments.
Colin McMillen, Paul Rybski, and Manuela Veloso.
Multi-Robot Systems: From Swarms to Intelligent Automata, Volume III, 2005.

MinneTAC Sales Strategies for Supply Chain TAC.
Wolfgang Ketter, Elena Kryzhnyaya, Steven Damer, Colin McMillen, Amrudin Agovic, John Collins, and Maria Gini.
Proceedings of the Third International Conference on Autonomous Agents and Multi-Agent Systems, New York, July 2004.

Analysis and Design of Supply-Driven Strategies in TAC-SCM.
Wolfgang Ketter, Elena Kryzhnyaya, Steven Damer, Colin McMillen, Amrudin Agovic, John Collins, and Maria Gini.
AAMAS04: Workshop on Trading Agent Design and Analysis, New York, July 2004.

A Real-Time Collision Warning System for Intersections.
Kristen Stubbs, Hemanth Arumugam, Osama Masoud, Colin McMillen, Harini Veeraraghavan, Ravi Janardan, and Nikos Papanikolopoulos.
Proceedings of Intelligent Transportation Systems America, Minneapolis, MN, USA, May 2003.

Heterogeneous Implementation of an Adaptive Robotic Sensing Team.
Bradley Kratochvil, Ian T. Burt, Andrew Drenner, Derek Goerke, Bennett Jackson, Colin McMillen, Christopher Olson, Nikolaos Papanikolopoulos, Adam Pfeifer, Sascha A. Stoeter, Kristen Stubbs, and David Waletzko.
Proceedings of the IEEE International Conference on Robotics and Automation, Taipei, Taiwan, May 2003.

Design of the UMN Multi-Robot System.
Andrew Drenner, Ian Burt, Brian Chapeau, Tom Dahlin, Bradley Kratochvil, Colin McMillen, Brad Nelson, Nikolaos Papanikolopoulos, Paul E. Rybski, Kristen Stubbs, David Waletzko, and Kemal Berk Yesin.
Multi-Robot Systems: From Swarms to Intelligent Automata, May 2002.

Mobility Enhancements to the Scout Robot Platform.
Andrew Drenner, Ian Burt, Tom Dahlin, Bradley Kratochvil, Colin McMillen, Brad Nelson, Nikolaos Papanikolopoulos, Paul E. Rybski, Kristen Stubbs, David Waletzko, and Kemal Berk Yesin.
Proceedings of the 2002 IEEE International Conference on Robotics and Automation, Washington D.C., USA, May 2002.

Ph.D. Thesis

Thresholded-Rewards Decision Problems: Acting Effectively in Timed Domains.
Colin McMillen.
Technical report CMU-CS-09-112, Carnegie Mellon University, April 2, 2009.

References:

Prof. Manuela Veloso
Prof. Luis von Ahn
Prof. Stephen Smith
Dr. Paul E. Rybski
Dr. Masahiro Fujita