1998 - 1999 CS Annual Report                                                                  Faculty
choices.gif (4488 bytes)


Bart Selman

Associate Professor
selman@cs.cornell.edu
http://www.cs.cornell.edu/home/selman

PhD Univ. of Toronto, 1991

I'm interested in the development of new formalisms and methods for artificial intelligence (AI) by combining a sound
theoretical approach with a principled experimental component. I focus on compute-intensive methods for AI.
Traditionally, general search and reasoning is largely avoided in AI by explicitly incorporating large amounts of
domain-specific knowledge. While such a knowledge-intensive approach has been successful in certain domains, such as automatic diagnosis, in other 
areas, such as planning or general reasoning, progress has been disappointing. However, recent advances in general search and reasoning methods combined with faster hardware and better implementations provide strong evidence that a compute-intensive approach is not only suitable for dealing with thecombinatorial nature of many AI formalisms, but may also be required to supplement domain-specific knowledge, especially considering the knowledge-acquisition bottleneck in terms of encoding highly specific domain knowledge. 

Part of my research is on fast general reasoning and search techniques, with an emphasis on stochastic methods. I also investigate the various sources of complexity in hard computational problems, using both theoretical and experimental methods. This work explores interesting connections between computer science, artificial intelligence, and statistical physics. In
addition, I study issues in problem representation, including the robustness of encodings, abstraction, compilation, and approximation methods. These issues are critical to the successful application in realistic domains of reasoning and search methods. In terms of applications, I am
particularly interested in challenge problems from planning, knowledge representation, machine learning, and data mining. Our planning system, BlackBox, developed jointly with Henry Kautz of AT&T Laboratories, is one of the fastest general purpose planning systems. I also pursue
applications in areas outside AI, such as, operations research and software/protocol verification. 

Awards  
  • Alfred P. Sloan Research Fellowship (1999-2001)  
  • NSF Faculty Early Career 
  • Development Award (1998-2002) 
University Activities  
  • Ph.D. Admissions Committee  
  • Coordinator of the AI Seminar Series 
  • Bits On Our Minds, Science Fair, Organizing Committee 
  • Cognitive Studies Undergraduate Committee 
  • Member: Field of Cognitive Studies 
  • Advisor: Cornell RoboSoccer Team 
Professional Activities 
  • Member: Executive Council of the American Association for Artificial Intelligence (elected in 
    '99). 
  • Co-Director: Summer School on Statistical Physics and Probabilistic Methods in
    Computer Science, Intl. Centre for Theoretical Physics, Trieste, Italy. 
  • Program co-Chair: 7th Intl. Conf. on Principles of Knowledge Representation and Reasoning; 6th Intl. Symposium on Artificial Intelligence and Mathematics 
  • Chair: Educational Forum, Sixteenth National Conference on Artificial Intelligence 
  • Organizing Committee and Workshop Chair: 5th Intl. Conf. on Artificial Intelligence Planning
    & Scheduling Systems  
  • Member: DARPA Info. Science and Technology Study Group on Probabilistic Methods in
    Computational Systems and Infrastructure  
  • Editor: Journal of Artificial Intelligence Research (JAIR) 
  • Editorial Board: Constraints: An International Journal, special issue of the Journal of
    Automated Reasoning  
  • Associate Editor: special issue of the Theoretical Computer Science 
  • Program Committee: Sixteenth National Conference on Artificial Intelligence (AAAI99), Sixteenth Intl. Joint Conference on Artificial Intelligence (IJCAI99), Fifth Intl. Conference on Principles and Practice of Constraint Programming (CP99), Question Answering System, AAAI Fall Symposium (1999), Computational Logic 2000
  • Referee/Reviewer: Artificial Intelligence Journal, JACM, Constraints, Journal of Automated Reasoning 
Lectures 
  • BLACKBOX: A new approach to the application of theorem proving to problem solving.
    Forum on Logic-Based Artificial Intelligence, Washington, DC, June 1999.  
  • Challenge problems for propositional reasoning and search. CS Colloquium, Univ. of Alberta, Edmonton, CA, May 1999.  
  • —. Natl. Program on Automated Deduction, Germany, July 1998. 
  • Understanding problem hardness: Recent developments and directions. DARPA/ISAT study group, Microsoft, Seattle, WA, Apr. 1999.  
  • Cognition: Lessons from artificial intelligence. Mind-Brain-Behavior Society, Cornell Univ., Ithaca, NY, Apr. 1999.  
  • Compute-intensive methods in AI. Rome Laboratory, Rome, NY, Nov 1998.  
  • —. JELIA-98, Schloss  Dagstuhl, Germany, Oct 1998.  
  • —. New opportunities for reasoning and search. Australian Natl. AI Conference, Brisbane, Australia, July 1998.  
  • Can computers think? High school forum, Cornell Univ., Ithaca, NY, Nov 1998.  
Publications  
  • Determining computational complexity from characteristic `phase transitions'. Nature 400,
    8     (1999) (with R. Monasson, S. Kirkpatrick, L. Troyansky, and R. Zecchina).  
  • Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning (1999) (with C. Gomes and N.Crato).  
  • 2+P-SAT: Relation of typical-case complexity to the nature of the phase transition. Random Structures (1999) (with R. Monasson, S. Kirkpatrick, L. Troyansky, and R. Zecchina).  
  • Heavy-tailed distributions in computational methods. Proc. Applications of Heavy Tailed Distributions in Economics, Engineering, and Statistics(1999) (with C. Gomes). 
  • Control knowledge in planning: benefits and tradeoffs. Proc. of the 16th Natl. Conf. on Artificial Intelligence (AAAI-99) (July 1999) (with Y.C. Huang and H. Kautz).  
  • Unifying SAT-based and graph-based planners. Proc. of the 15th Intl. Joint Conf. on Artificial
    Intelligence (IJCAI-97)     (1999) (with H. Kautz).  
  • Boosting combinatorial search through randomization. Proc. of the 15th Natl. Conf. on Artificial Intelligence (AAAI-98) (1998) (with C. Gomes and H. Kautz).