I'm doing a research project with David Aha at the Naval Research Lab on how AI can be used to overcome information overload in multiparticipant chat (e.g., IRC). The NY Times recently wrote an article about this from an Air Force / Army viewpoint. While this research project is in context of problems seen within the US Navy, we're taking a general-AI approach to this to make it applicable to other domains.
My PhD research mostly focused on the traveling tournament problem (TTP), a brutally-hard, combinatorial optimization problem from the sports scheduling literature (I call it the traveling salesman problem on steroids). I approached this problem using two types of techniques: metaheuristics (ant colony optimization) and heuristic search (DFS* and IDA*). While the ACO approach did average, the heuristic search approaches did surprisingly well, which can be seen on the TTP website with all the optimal solutions we (Uthus, Riddle, and Guesgen) found. The DFS*-based approach (presented at CPAIOR 2009) solved CIRC8, SUPER4-10, GALAXY4-8 and found new lower bounds for NL10-12, CIRC10, SUPER12-14, and GALAXY10. The IDA*-based approach (published in Journal of Scheduling) later solved NL10, CIRC10, and GALAXY10. All optimal solutions are available under the Files section.
PhD Computer Science (2010): University of Auckland, supervisors
Patricia Riddle and Hans Guesgen
MSc Computer Science (2006): University of Auckland, supervisors Hans Guesgen and Patricia Riddle
BSc Computer Science, Minor International and Global Studies (2004): University of California, Davis
Education Abroad Program (2003): Lund University
- Uthus, D.C., & Aha, D.W. (2013). Multiparticipant Chat Analysis: A Survey. Artificial Intelligence. doi: 10.1016/j.artint.2013.02.004 [Elsevier link]
- Uthus, D.C., Riddle, P.J., & Guesgen, H.W. (2012). Solving the Traveling Tournament Problem with Iterative-Deepening A*. Journal of Scheduling, 15(5), 601-614. doi: 10.1007/s10951-011-0237-x [Springer Link]
Conferences & Symposia
- Uthus, D.C., & Aha, D.W. (In press). Extending Word Highlighting in Multiparticipant Chat. Proceedings of the Florida Artificial Intelligence Research Society Conference
- Uthus, D.C., & Aha, D.W. (2013). The Ubuntu Chat Corpus for Multiparticipant Chat Analysis. Papers from the 2013 AAAI Spring Symposium on Analyzing Microtext (pp. 99-102). Stanford, CA: AAAI Press. [AAAI Link] [Presentation & Poster]
- Uthus, D.C., Riddle, P.J., & Guesgen, H.W. (2009). An Ant Colony Optimization Approach to the Traveling Tournament Problem. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (pp. 81-88). Montréal, Canada: ACM. doi:10.1145/1569901.1569913 [ACM Link | Presentation Slides]
- Uthus, D.C., Riddle, P.J., & Guesgen, H.W. (2009). DFS* and the Traveling Tournament Problem. Proceedings of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 279-293). Pittsburgh, PA: Springer-Verlag. doi:10.1007/978-3-642-01929-6_21 [Springer Link | Presentation Slides]
- Uthus, D.C., Riddle, P.J., & Guesgen, H.W. (2008). Ant Colony Optimization and the Single Round Robin Maximum Value Problem. Proceedings of the 6th International Conference on Ant Colony Optimization and Swarm Intelligence (pp. 243-250). Brussels, Belgium: Springer-Verlag. doi:10.1007/978-3-540-87527-7_23 [Springer Link]
- Uthus, D.C., & Aha, D.W. (2011). Plans Toward Automated Chat Summarization. Proceedings of the Workshop on Automatic Summarization for Different Genres, Media, and Languages (pp.1-7). Portland, OR: Association for Computational Linguistics. [ACL Link]
- Hovy, E., Markman, V., Martell, C., & Uthus, D.C. (Eds.) (2013). Papers from the 2013 AAAI Spring Symposium on Analyzing Microtext. Technical Report SS-13-01. Stanford, CA: AAAI Press. [AAAI Link]
- Aha, D.W., Oard, D.W., Ramachandran, S., & Uthus, D.C. (Eds.) (2011). Papers from the AAAI Workshop on Analyzing Microtext. Technical Report WS-11-05. San Francisco, CA: AAAI Press. [AAAI Link]
- Agmon, N., Agrawal, V., Aha, D.W., Aloimons, Y., Buckley, D., Doshi, P., Geib, C., Grasso, F., Green, N., Johnson, B., Kaliski, B., Kiekintveld, C., Law, E., Lieberman, H., Mengshoel, O.J., Metzler, T., Modayil, J., Oard, D.W., Onder, N., O'Sullivan, B., Pastra, K., Precup, D., Ramachandran, S., Reed, C., Sariel-Talay, S., Selker, T., Shastri, L., Singh, S., Smith, S.F., Srivastava, S., Sukthankar, G., Uthus, D.C., & Williams, M.-A. (2012). Reports of the AAAI 2011 Conference Workshops. AI Magazine, 33(1), 57-70. [AAAI Link]
- Uthus, D.C., Riddle, P.J., & Guesgen, H.W. (2013). Solving the Traveling Tournament Problem with Iterative-Deepening A*. ICAPS 2013 Journal Presentation Track. Rome, Italy: AAAI Press.
- Williams, B., Uthus, D.C., & Aha, D.W. (2012). Automated Chat Generator. Technical Note AIC-12-131. Washington, DC: Naval Research Laboratory, Navy Center for Applied Research in Artificial Intelligence.
- Uthus, D.C. (2010). Sports Scheduling: An Artificial Intelligence Approach. PhD Thesis.
- Uthus, D.C. (2006). Hierarchical Partitioned Framework for the Ant Colony Optimization Metaheuristic. MSc Thesis.
- Overcoming Information Overload in Navy Chat. NRC Postdoctoral Colloquium Series, Naval Research Laboratory, Washington, DC, 22 November, 2011.
- Overcoming Information Overload in Navy Chat. University of Maryland, College Park, MD, 05 October, 2011.
- Overcoming Information Overload in Navy Chat. USC Information Sciences Institute, Marina del Rey, CA, 05 August, 2011.
- DFS* and the Traveling Tournament Problem. NASA Ames Research Center, Moffett Field, CA, 20 July, 2009. [Presentation Slides]
- DFS* and the Traveling Tournament Problem. NASA Jet Propulsion Laboratory, Pasadena, CA, 07 July, 2009. Same presentation slides as Ames.
AAAI 2013 Spring Symposium on Analyzing Microtext (Co-Chair): 2012 - 2013
AAAI-11 Workshop on Analyzing Microtext (Co-Chair): 2011 [Presentations]
New Zealand Computer Science Student Research Conference '09 (Treasurer): 2008 - 2009
Auckland University Underwater Club (Secretary): 2007
ACL (Member): 2011 - Present
AAAI (Member): 2011 - Present
ACM (Member): 2009 - Present
The Ubuntu Chat Corpus: Here
Optimal solutions for NL, CIRC, SUPER, and GALAXY, sizes 4 to 10 teams: TTPOptimalSolutions.txt
Galaxy instances for the TTP (also available on Michael Trick's TTP website along with our best results): GalaxySet.zip
Super 14 Rugby League instances for the TTP (also available on the TTP website along with our best results): Super14.zip
Problem instance files used for the single round robin maximum value problem: srrmvp.zip
Ant Colony Optimization
Challenge Traveling Tournament Instances
Classification of Literature on Sports Scheduling
Richard Hamming's "You and Your Research"
San Jose Sharks
Updated: 19th April, 2013 ⚙ Copyright © 2008-13 David Uthus ⚙ Valid HTML 4.01 Strict