Papers by Wheeler Ruml

1. Heuristic Search and Optimization
2. Planning and Scheduling
3. Cognitive Modeling
4. Ad-hoc Networking
5. Intelligent Interfaces
6. Other

Overview and Samples

This invited talk from SoCS-11 provides an overview of my work on suboptimal search for specialists in AI. This tutorial from ICAPS-11 provides a basic survey of suboptimal search.

Here are four representative papers:

• Jordan T. Thayer and Wheeler Ruml, Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates, Proceedings of the Twenty-second International Joint Conference on Artificial Intelligence (IJCAI-11), 2011.

• Jordan T. Thayer, Austin Dionne, and Wheeler Ruml, Learning Inadmissible Heuristics During Search, Proceedings of the Twenty-first International Conference on Automated Planning and Scheduling (ICAPS-11), 2011.

• Ethan Burns, Sofia Lemons, Wheeler Ruml, and Rong Zhou, Best-First Heuristic Search for Multicore Machines, Journal of Artificial Intelligence Research, volume 39, pages 689-743, 2010.

• Wheeler Ruml, Minh B. Do, Rong Zhou, and Markus P.J. Fromherz, On-line Planning and Scheduling: An Application to Controlling Modular Printers, Journal of Artificial Intelligence Research, volume 40, pages 415-468, 2011.

Heuristic Search and Optimization

Time-sensitive Search

• Austin J. Dionne, Jordan T. Thayer, and Wheeler Ruml, Deadline-Aware Search Using On-line Measures of Behavior, Proceedings of the Symposium on Combinatorial Search (SoCS-11), 2011. Here's Jordan's poster and a few talk slides. If you are interested in this topic, you might also want to see Austin's MS Thesis.

• David M. Bond, Niels A. Widger, Wheeler Ruml and Xiaoxun Sun, Real-Time Search in Dynamic Worlds, Proceedings of the Symposium on Combinatorial Search (SoCS-10), 2010. David's talk slides. Videos: LSS-LRTA*, D*lite, Real-time D*, Real-time D* again.

• Jordan Thayer and Wheeler Ruml, Anytime Heuristic Search: Frameworks and Algorithms, Proceedings of the Symposium on Combinatorial Search (SoCS-10), 2010. Jordan's Poster.

• Silvia Richter, Jordan T. Thayer, and Wheeler Ruml, The Joy of Forgetting: Faster Anytime Search via Restarting, Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS-10) , 2010. Silvia's talk slides.
  • An earlier version of this paper was published in the Proceedings of the International Symposium on Combinatorial Search (SoCS-09), 2009.

• Wheeler Ruml and Minh B. Do, Best-first Utility-Guided Search, Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), 2007. talk slides.
  • A preliminary version of the work appeared as Wheeler Ruml and Elisabeth H. Crawford, Best-first Utility-Guided Search, Working Notes of the IJCAI-05 Workshop on Planning and Learning in A Priori Unknown or Dynamic Domains, 2005.

• Ying Lu, Lara S. Crawford, Wheeler Ruml, Markus P. J. Fromherz, Feedback Control for Real-Time Solving, Working Notes of the CP-04 Workshop on Constraint Solving under Change and Uncertainty (Changes '04), 2004.

Other Suboptimal Search

• Christopher Wilt and Wheeler Ruml, When does Weighted A* Fail?, Proceedings of the Symposium on Combinatorial Search (SoCS-12), 2012. Chris' talk slides.

• Jordan Thayer, Roni Stern, Ariel Felner, and Wheeler Ruml, Faster Bounded-Cost Search Using Inadmissible Estimates, Proceedings of the Twenty-second International Conference on Automated Planning and Scheduling (ICAPS-12), 2012. Jordan's talk slides.

• Wheeler Ruml, Planning Algorithms: When Optimal Just Isn't Good Enough, an invited talk given at the University of Massachusetts Lowell (November, 2011), Tufts University (September, 2012), Harvard University (September, 2012), and Vassar College (November, 2012). Streaming video of the Harvard talk is available here.

• Wheeler Ruml, Search Algorithms as Agents, an invited talk given at the Symposium on Combinatorial Search (SoCS-11), July 2011.

• Christopher Wilt and Wheeler Ruml, Cost-Based Heuristic Search is Sensitive to the Ratio of Operator Costs, Proceedings of the Symposium on Combinatorial Search (SoCS-11), 2011.

• Jordan T. Thayer and Wheeler Ruml, Using Solution Length Estimates in Heuristic Search, a tutorial given at the Twenty-first International Conference on Automated Planning and Scheduling (ICAPS-11), June 2011.

• Jordan T. Thayer and Wheeler Ruml, A Survey of Suboptimal Search Algorithms, a tutorial given at the Twenty-first International Conference on Automated Planning and Scheduling (ICAPS-11), June 2011.

• Jordan T. Thayer and Wheeler Ruml, Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates, Proceedings of the Twenty-second International Joint Conference on Artificial Intelligence (IJCAI-11), 2011. Jordan's talk slides. A recorded video of his talk is available here (look for `Rooms 122-123', Jordan starts around 39:30).
  • A preliminary summary appeared as Jordan Thayer and Wheeler Ruml, Finding Acceptable Solutions Faster Using Inadmissible Information, Proceedings of the Symposium on Combinatorial Search (SoCS-10), 2010. Jordan's talk slides.

  • A longer preliminary version was made available as UNH CS Technical Report 10-01, 2010.

• Jordan T. Thayer, Austin Dionne, and Wheeler Ruml, Learning Inadmissible Heuristics During Search, Proceedings of the Twenty-first International Conference on Automated Planning and Scheduling (ICAPS-11), 2011. Jordan's talk slides and a nice recorded video of his presentation at ICAPS.

• Christopher Wilt, Jordan Thayer and Wheeler Ruml, A Comparison of Greedy Search Algorithms, Proceedings of the Symposium on Combinatorial Search (SoCS-10), 2010. Chris' Poster.
  • Additional work along these lines is available in Christopher Wilt, Jordan Thayer and Wheeler Ruml, Selecting a Greedy Search Algorithm, UNH CS Technical Report 10-07, 2011.

• Jordan T. Thayer, Wheeler Ruml, and Jeff Kreis, Using Distance Estimates in Heuristic Search: A Re-evaluation, Proceedings of the International Symposium on Combinatorial Search (SoCS-09), 2009. Jordan's Poster.
  • A shorter version of this paper was published as: Jordan T. Thayer and Wheeler Ruml, Using Distance Estimates in Heuristic Search, Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS-09), 2009.

• Jordan T. Thayer and Wheeler Ruml, Faster Than Weighted A*: An Optimistic Approach to Bounded Suboptimal Search, Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS-08), 2008. Jordan's talk slides.

• Jordan T. Thayer, Wheeler Ruml, and Ephrat Bitton, Fast and Loose in Bounded Suboptimal Heuristic Search, Proceedings of the First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR-08), 2008. Jordan's talk slides.
  • A preliminary version of this work was presented at the Third North East Student Colloquium on Artificial Intelligence (NESCAI-08).

Parallel, External Memory, and Linear Memory Search

• Ethan Burns and Wheeler Ruml, Iterative-Deepening Search with On-line Tree Size Prediction, Proceedings of the Sixth International Conference on Learning and Intelligent Optimization (LION), 2012. Ethan's talk slides.

• Matthew Hatem, Ethan Burns, and Wheeler Ruml, Heuristic Search for Large Problems With Real Costs, Proceedings of the Twenty-fifth AAAI Conference on Artificial Intelligence (AAAI-11), 2011. Matt's talk slides.

• Ethan Burns, Sofia Lemons, Wheeler Ruml, and Rong Zhou, Best-First Heuristic Search for Multicore Machines, Journal of Artificial Intelligence Research, volume 39, pages 689-743, 2010.
  • A summary of this work appeared as: Ethan Burns, Sofia Lemons, Wheeler Ruml, and Rong Zhou, Parallel Best-First Search: The Role of Abstraction, Proceedings of the AAAI-10 Workshop on Abstraction, Reformulation, and Approximation (WARA-10), 2010. Ethan's talk slides.

  • An earlier summary appeared as: Ethan Burns, Seth Lemons, Wheeler Ruml, and Rong Zhou, Parallel Best-First Search: Optimal and Suboptimal Solutions, Proceedings of the International Symposium on Combinatorial Search (SoCS-09), 2009. Seth's talk slides.

• Ethan Burns, Seth Lemons, Wheeler Ruml, and Rong Zhou, Suboptimal and Anytime Heuristic Search on Multi-Core Machines, Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS-09) , 2009. Ethan's talk slides.

• Ethan Burns, Seth Lemons, Rong Zhou, and Wheeler Ruml, Best-First Heuristic Search for Multi-Core Machines, Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09), 2009. Ethan's talk slides.

Motion Planning

• Jarad Cannon, Kevin Rose, and Wheeler Ruml, Real-time Motion Planning with Dynamic Obstacles, Proceedings of the Symposium on Combinatorial Search (SoCS-12) , 2012. talk slides. Jarad's MS thesis. Kevin's MS thesis.

• Scott Kiesel, Ethan Burns, and Wheeler Ruml, Abstraction-guided Sampling for Motion Planning, UNH CS Technical Report 12-01, 2012.
  • A shorter version of this paper was published as: Scott Kiesel, Ethan Burns, and Wheeler Ruml, Abstraction-guided Sampling for Motion Planning, Symposium on Combinatorial Search (SoCS-12), 2012.

• Scott Kiesel, Ethan Burns, Christopher Wilt, and Wheeler Ruml, Integrating Vehicle Routing and Motion Planning, Proceedings of the Twenty-second International Conference on Automated Planning and Scheduling (ICAPS-12), 2012. Scott's talk slides.

Hierarchical Search

• Michael J. Leighton, Wheeler Ruml, and Robert C. Holte, Faster Optimal and Suboptimal Hierarchical Search, Proceedings of the Symposium on Combinatorial Search (SoCS-11), 2011.

• Bradford Larsen, Ethan Burns, Wheeler Ruml, and Robert C. Holte, Searching Without a Heuristic: Efficient Use of Abstraction, Proceedings of the Twenty-fourth AAAI Conference on Artificial Intelligence (AAAI-10), 2010. Brad's talk slides. Note: the psuedo-code for switchback in this paper has a bug - see the SoCS-11 paper for a corrected version.

Methodology, Milieu

• Nathan R. Sturtevant, Ariel Felner, Maxim Likhachev, Wheeler Ruml, Heuristic Search Comes of Age (invited paper), Proceedings of the Twenty-sixth AAAI Conference on Artificial Intelligence (AAAI-12), 2012.

• Ethan Burns, Matthew Hatem, Michael J. Leighton, and Wheeler Ruml, Implementing Fast Heuristic Search Code, Proceedings of the Symposium on Combinatorial Search (SoCS-12), 2012. Ethan's code.

• Wheeler Ruml, The Logic of Benchmarking: A Case Against State-of-the-Art Performance, Proceedings of the Symposium on Combinatorial Search (SoCS-10), 2010. talk slides.

Constraint Satisfaction and Combinatorial Optimization

• Kevin Rose, Ethan Burns, and Wheeler Ruml, Best-first Search for Bounded-depth Trees, Proceedings of the Symposium on Combinatorial Search (SoCS-11), 2011.

• Hai Fang and Wheeler Ruml, Complete Local Search for Propositional Satisfiability. Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI-04), 2004.

• Wheeler Ruml, Adaptive Tree Search. Ph.D. thesis, Harvard University, May, 2002.

• Wheeler Ruml, Heuristic Search in Bounded-depth Trees: Best-Leaf-First Search. Working Notes of the AAAI-02 Workshop on Probabilistic Approaches in Search, 2002.
  • A preliminary version was made available as Harvard CS Technical Report TR-01-02.

• Wheeler Ruml, Using Prior Knowledge with Adaptive Probing, Working Notes of the AAAI 2001 Fall Symposium on Using Uncertainty within Computation, pp. 116-120.

• Wheeler Ruml, Stochastic Tree Search: Where to Put the Randomness?, Working Notes of the IJCAI-01 Workshop on Stochastic Search, pp. 43-47.

• Wheeler Ruml, Incomplete Tree Search using Adaptive Probing, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), pp. 235-241.
  • A preliminary version of this paper was made available as Harvard CS Technical Report TR-02-01.

• Wheeler Ruml, Adam Ginsburg, and Stuart Shieber, Speculative Pruning for Boolean Satisfiability, Harvard CS Technical Report TR-02-99.

• Wheeler Ruml, Joe Marks, Stuart Shieber, and Tom Ngo, Seed-Growth Heuristics for Graph Bisection. Harvard CS Technical Report TR-10-99.
  • A preliminary version was published as Joe Marks, Wheeler Ruml, Stuart Shieber, and Tom Ngo, A Seed-Growth Heuristic for Graph Bisection, Proceedings of Algorithms and Experiments '98. Also available as Harvard CS Technical Report TR-01-98.

• Wheeler Ruml, J. Thomas Ngo, Joe Marks, and Stuart Shieber, Easily Searched Encodings for Number Partitioning, Journal of Optimization Theory and Applications, volume 89, number 2, 1996. Also available as Harvard CS Technical Report TR-10-94r.

• Wheeler Ruml, Stochastic Approximation Algorithms for Number Partitioning, undergraduate thesis and Harvard CS Technical Report TR-17-93.

Planning and Scheduling

Probabilistic Planning

• Ethan Burns, J. Benton, Wheeler Ruml, Minh Do, and Sungwook Yoon, Anticipatory On-line Planning, Proceedings of the Twenty-second International Conference on Automated Planning and Scheduling (ICAPS-12), 2012. Ethan's talk slides.
  • An earlier iteration of this work was published as: Allen Hubbe, Wheeler Ruml, Sungwook Yoon, J. Benton, and Minh B. Do, On-line Anticipatory Planning, Proceedings of the ICAPS-08 Workshop on A Reality Check for Planning and Scheduling Under Uncertainty, 2008.

• Sungwook Yoon, Wheeler Ruml, J. Benton, and Minh B. Do, Improving Determinization in Hindsight for On-line Probabilistic Planning, Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS-10), 2010.

• Seth Lemons, J. Benton, Wheeler Ruml, Minh B. Do, and Sungwook Yoon, Continual On-line Planning as Decision-Theoretic Incremental Heuristic Search, Proceedings of the AAAI Spring Symposium on Embedded Reasoning, 2010.

On-line Planning

• Wheeler Ruml, Minh B. Do, Rong Zhou, and Markus P.J. Fromherz, On-line Planning and Scheduling: An Application to Controlling Modular Printers, Journal of Artificial Intelligence Research, volume 40, pages 415-468, 2011.
  • A summary with an emphasis on planning was published as: Minh B. Do, Wheeler Ruml, and Rong Zhou, On-line Planning and Scheduling: An Application to Controlling Modular Printers, Proceedings of the Twenty-third AAAI Conference on Artificial Intelligence (AAAI-08), 2008.

  • A summary with an emphasis on hardware was published as: David Biegelsen, Lara Crawford, Minh Do, Dave Duff, Craig Eldershaw, Markus Fromherz, Haitham Hindi, Greg Kott, Dan Larner, Barry Mandel, Steve Moore, Bryan Preas, Wheeler Ruml, Greg Schmitz, Lars Swartz, and Rong Zhou, Integrated Parallel Printing Systems with Hypermodular Architecture, IS&T/SPIE Conference on Electronic Imaging Symposium on Parallel Processing for Imaging Applications, 2011.

• Minh B. Do, Wheeler Ruml, and Rong Zhou, Planning for Modular Printers: Beyond Productivity, Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS-08), 2008.

• J. Benton, Minh B. Do, and Wheeler Ruml, A Simple Testbed for On-line Planning, Proceedings of the ICAPS-07 Workshop on Moving Planning and Scheduling Systems into the Real World, 2007.

• Haitham Hindi and Wheeler Ruml, Network Flow Modeling for Flexible Manufacturing Systems with Re-entrant Lines, Proceedings of the 45th IEEE Conference on Decision and Control (CDC-06), 2006.

• Minh B. Do and Wheeler Ruml, Lessons Learned in Applying Domain-independent Planning to High-speed Manufacturing, Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS-06), 2006.

• Wheeler Ruml, Minh B. Do, and Markus P. J. Fromherz, On-line Planning and Scheduling for High-speed Manufacturing, Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS-05), 2005. Winner of the ICAPS-05 Best Application Paper Award!
  • An earlier version appeared as: Wheeler Ruml and Markus P. J. Fromherz, On-line Planning and Scheduling in a High-speed Manufacturing Domain, Proceedings of the ICAPS-04 Workshop on Integrating Planning into Scheduling, 2004.

Cognitive Modeling

• Wheeler Ruml, Alfonso Caramazza, Rita Capasso, and Gabriele Miceli, Interactivity and Continuity in Normal and Aphasic Language Production, Cognitive Neuropsychology, volume 22, number 2, pp. 131-168, 2005.

• Wheeler Ruml, Constructing Distributed Representations using Additive Clustering, Advances in Neural Information Processing Systems 14 (NIPS-01), MIT Press, 2002.
  • A slightly different version is available as Assigning Features using Additive Clustering, Harvard CS Technical Report TR-04-01.

• Alfonso Caramazza, Costanza Papagno, and Wheeler Ruml, The Selective Impairment of Phonological Processing in Speech Production, Brain and Language, volume 75, number 3, December, 2000, pages 428-450.

• Wheeler Ruml, Alfonso Caramazza, Jennifer R. Shelton, and Doriana Chialant, Testing Assumptions in Computational Theories of Aphasia, Journal of Memory and Language, volume 43, number 2, August, 2000, pages 217-248.

• Wheeler Ruml and Alfonso Caramazza, An Evaluation of a Computational Model of Lexical Access: Comments on Dell et al. (1997), Psychological Review, volume 107, number 3, July, 2000, pages 609-634.

Ad-hoc Networking

• Yi Shang, Wheeler Ruml, and Markus P. J. Fromherz, Positioning Using Local Maps, Ad Hoc Networks, volume 4, number 2, page 240-253, 2006.

• Yi Shang, Wheeler Ruml, Ying Zhang and Markus P. J. Fromherz, Localization from Connectivity in Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, volume 15, number 11, pages 961--974, 2004.

• Yi Shang and Wheeler Ruml, Improved MDS-Based Localization, Proceedings of the 23rd Conference of the IEEE Communications Society (Infocom '04), 2004.

• Yi Shang, Wheeler Ruml, Ying Zhang and Markus P. J. Fromherz, Localization from Mere Connectivity, Proceedings of the Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '03), 2003.

Intelligent Interfaces

• Brad Andalman, Kathy Ryall, Wheeler Ruml, Joe Marks, and Stuart Shieber, Design Gallery Browsers Based on 2D and 3D Graph Drawing, Proceedings of Graph Drawing '97, 1997.

• Joe Marks, Brad Andalman, Paul Beardsley, William Freeman, Sarah Gibson, Jessica Hodgins, Tom Kang, Brian Mirtich, Hanspeter Pfister, Wheeler Ruml, Kathy Ryall, Josh Seims, and Stuart Shieber, Design Galleries: A General Approach to Setting Parameters for Computer Graphics and Animation, SIGGRAPH, 1997.

Other

• Wheeler Ruml, Job Hunting in Industry and Academia, invited talk at the ICAPS-08, ICAPS-10, and ICAPS-13 Doctoral Consortia.