Conference Program

To view this page ensure that Adobe Flash Player version 9.0.124 or greater is installed.

Please login or register to make a comment!

...Description...... more. less.

Texas at Austin) and William Cheetham (General Electric Re- search) Special Track on ArtiLcial Intelligence and the Web Cochairs Tim Finin (University of Maryland, Balti- more County) and Dragomir Radev (Univer- sity of Michigan) Special Track on Integrated Intelligent Capabilities Cochairs Art Graesser (University of Memphis) and Reid Simmons (Carnegie Mellon University) Senior Member Papers Cochairs Kathy McKeown (Columbia University) and Dan Weld, University of Washington AAAI Nectar Papers Cochairs AnHai Doan (University of Illinois at Ur- bana-Champaign) and Elaine Rich (Universi- ty of Texas at Austin) Member Abstracts and Posters Cochairs Dieter Fox (University of Washington) and Ion Muslea (Language Weaver) Tutorial Forum Cochairs Qiang Yang (Hong Kong University of Sci- ence and Technology) and Carla Gomes (Cornell University) Workshop Cochairs Joyce Chai (Michigan State University) and Keith Decker (University of Delaware) Doctoral Consortium Chair and Cochair Kiri Wagstaff (Jet Propulsion Laboratory) and Terran Lane (University of New Mexico) Student Abstract and Poster Cochairs Maria Fox (University of Strathclyde), Sailesh Ramakrishnan (University of Michi- gan), and Lynn Andrea Stein (Franklin W. Olin College of Engineering) Intelligent Systems Demonstrations Cochairs Rob Miller (Massachusetts Institute of Tech- nology) and Biplav Srivastava (IBM India Re- search Labs) Game Playing Competition Chair Michael Genesereth (Stanford University) Mobile Robot Competition and Exhibition General Cochairs Paul Rybski (Carnegie Mellon University) and Jeffrey Forbes (Duke University) Poker Competition Cochairs Jonathan Schaeffer (University of Alberta) and Michael Littman (Rutgers University) Sponsorship Chair Illah Nourbakhsh (Carnegie Mellon University) Student Participation Associate Chairs Martin Michalowski and Matt Michelson (In- formation Sciences Institute, University of Southern California) Technical Program Software Chair Ken Barker (University of Texas at Austin) A complete listing of the AAAI-06 and IAAI-06 program committee members ap- pears in the conference proceedings. Sponsoring Organizations AAAI gratefully acknowledges the gener- ous contributions of the following organi- zations to AAAI-06: I National Science Foundation I Naval Research Laboratory I Microsoft Research I The Boeing Company I Michael Genesereth I ITA Software, Inc. I Google I Intel Corporation I Yahoo! Research I Idaho National Laboratory I IBM Research I Ask Jeeves I Intelligent Information Systems Institute, Cornell University I Teknowledge Corporation I ACM/SIGART I K-Team/RoadNarrows I MobileRobots Inc. The Defense Advanced Projects Research Agen- cy also provided funds. Awards All AAAI-06, IAAI-06, and AAAI Special Awards will be presented Tuesday, July 18, 8:30 3 9:00 AM ,in the Commonwealth Complex on the Harbor Level of the World Trade Center. AAAI-06 Awards The AAAI-06 Awards will be presented by program cochairs Yolanda Gil and Ray- mond C. Mooney. Outstanding Paper Awards Model Counting: A New Strategy for Obtain- ing Good Bounds by Carla P. Gomes, Ashish Sabharwal, and Bart Selman (Cornell Uni- versity) Towards an Axiom System for Default Logic by Gerhard Lakemeyer (Aachen University of Technology), and Hector J. Levesque (University of Toronto) Outstanding Senior Program Committee Member Award Brian Williams (Massachusetts Institute of Technology) Outstanding Program Committee Member Awards Ernie Davis (New York University), and Rosemary Emery-Montemerlo (Stanford University) IAAI-06 Deployed Applications Awards The six IAAI-06 Deployed Application Awards will be announced by the IAAI-06 chair Bruce Porter and cochair William Cheetham. Please see the schedule for pa- per titles. Certi[cates will be presented during paper sessions. Robert S. Engelmore Memorial Award and Lecture The Robert S. Engelmore Award is spon- sored by IAAI-06 and AI Magazine, and will be presented by Bruce Porter and William Cheetham, IAAI-06 chair and cochair, and David B. Leake, editor-in- chief, AI Magazine. The award and lecture was established in 2003 to honor Robert Engelmore's extraordinary service to AAAI, AI Magazine, and the AI applica- tions community, and his contributions to applied AI. The 2006 award will be pre- sented to Bruce Buchanan, University 2C ONTENTS & A CKNOWLEDGEMENTS & S PONSORS & A WARDS Contents Acknowledgments / 2 Awards / 2 33 Conference at a Glance / 5 Doctoral Consortium / 4 Exhibition / 16 Game Playing Competition / 17 General Information / 19 IAAI-06 Program / 8 313 Intelligent Systems Demonstrations / 17 Invited Talks / 6 37 Poker Competition / 18 Posters / 14 Registration / 21 Robot Competition and Exhibition / 18 Special Events and Programs / 3 34 Special Meetings / 7 Sponsoring Organizations / 2 Technical Program / 8 313 Tutorial Forum / 6 Workshop Program /4 Professor of Computer Science Emeritus (University of Pittsburgh), for leadership in arti[cial intelligence and pioneering contributions to knowledge-based sys- tems, machine learning, and automated discovery, along with signi[cant applica- tions in medicine, biology and chemistry. The lecture will be held Wednesday, July 19, 4:20 PM , in Harborview II. AAAI Special Awards Special awards will be presented by Ronald J. Brachman, Awards Committee chair and AAAI past president, and Alan Mackworth, AAAI president. Classic Paper Award The 2006 AAAI Classic Paper Award will be given jointly to the authors of two pa- pers considered to be the most in\uential from the Sixth National Conference on Ar- ti[cial Intelligence, held in 1987 in Seat- tle, Washington. The 2006 award winners are Philip E. Agre and David Chapman for Pengi: An Implementation of a Theory of Activity and Michael P. Georgeff and Amy L. Lansky for Reactive Reasoning and Planning. The authors of two additional papers have received honorable mention, includ- ing Richard E. Korf for Real-Time Heuristic Search: First Results and Judea Pearl and Thomas Verma for The Logic of Represent- ing Dependenciesby Directed Graphs. Distinguished Service Award The AAAI Distinguished Service Award recognizes one individual each year for extraordinary service to the AI communi- ty. The 2006 award winner is Edward Feigenbaum (Kumagai Professor of Com- puter Science and Coscienti[c Director, Knowledge Systems Laboratory, Stanford University) for a lifetime of service to ar- ti[cial intelligence as a tireless and effec- tive champion of the [eld, including sem- inal contributions to the theory and prac- tice of knowledge-based systems, coedi- torship of the [rst major collection of AI papers, mentorship of numerous leading AI researchers, facilitation of the com- mercialization of AI technology, and ser- vice to the AI and computer science com- munities in many key leadership roles, in- cluding president of AAAI and chief sci- entist of the US Air Force. General Game Playing Competition The AAAI General Game Playing Compe- tition is designed to test the abilities of general game playing systems by compar- ing their performance on a variety of games. The competition will consist of two phases: a quali[cation round and a runoff competition during AAAI. A K EYNOTE A DDRESS &A WARDS 3 Keynote Address Tim Berners-Lee (Director, World Wide Web Consortium) Tuesday, July 18, 9:00 3 10:00 AM Commonwealth Complex, World Trade Center The relationship between AI and the semantic web has been something that has pro- voked a lot of heated corridor discussion over the years. This talk will try to outline what the semantic web is and is not, at a conference where there may be some an- niversary re\ection on what AI is and is not. It is not always obvious how to transfer existing AI techniques into a fractal weblike space, or what the effect will be. But it is certainly exciting. A graduate of Oxford University, England, Berners-Lee now holds the 3Com Founders chair at the Laboratory for Computer Science and Arti[cial Intelligence Lab (CSAIL) at the Massachusetts Institute of Technology (MIT), where he leads the Decentralized Information group (DIG). He directs the World Wide Web Consortium, an open forum of companies and organizations with the mission to lead the Web to its full potential. With a background of system design in real-time communications and text processing software development, in 1989 he invented the World Wide Web, an internet-based hy- permedia initiative for global information sharing, while working at CERN, the Euro- pean Particle Physics Laboratory. He wrote the [rst web client (browser-editor) and server in 1990. $10,000 award will be presented to the winning entrant. AAAI gratefully ac- knowledges the generous contribution of Michael Genesereth, who has made this award possible. The Award will be pre- sented by Michael Genesereth, Competi- tion Chair. 2006 AAAI Fellows Recognition Dinner Each year, the American Association for Arti[cial Intelligence recognizes a small number of members who have made sig- ni[cant sustained contributions to the [eld of arti[cial intelligence, and who have attained unusual distinction in the profession. AAAI is pleased to announce the seven newly elected Fellows for 2006: Fahiem Bacchus (University of Toronto) Craig Boutilier (University of Toronto) Anthony G. Cohn (University of Leeds) Gregory F. Cooper (University of Pittsburgh) Jude W. Shavlik (University of Wisconsin) Oliviero Stock (ITC-IRST) Sebastian Thrun (Stanford University) New and Special Programs AAAI-06 will include several new and spe- cial programs as AI celebrates the 50th an- niversary of the Dartmouth Conference. The program chairs have added two spe- cial tracks to the technical program 4 AI & the Web and Integrated Intelligent Ca- pabilities 4 which will run consecutively in the Cityview I room in the World Trade Center, July 18-19. AAAI Senior Member papers and Nectar papers (new scienti[c and technical advances in research) have been integrated into the technical pro- gram schedule throughout the confer- ence, and AAAI members will present posters during the poster session on Wednesday evening, July 19. AAAI Fellows 50th Anniversary Panel A special Fellows 50th Anniversary Panel will be held Tuesday, July 18, 5:30 3 6:30 pm in the Commonwealth Complex of the World Trade Center. Open ScientiLc Questions Blog Please take a moment to visit this exhibit in the registration area on the upper level of the World Trade Center. An offshoot of the recent AAAI Fellows Symposium, AAAI-06 conference attendee feedback will be solicited regarding open scienti[c questions that will help shape the next 50 years of research in AI. AAAI Fellow / Student Lunches A small number of students will have the opportunity to chat with a AAAI Fellow over an informal lunch during the confer- ence. For more information, check out the Student Activities site described below. Opening Reception The AAAI-06 Opening Reception will be held Monday, July 17, 6:00 3 7:00 PM in the Plaza Ballroom of the Seaport Hotel. This event will provide the traditional op- portunity for attendees to socialize in a re- laxed setting prior to the beginning of the [rst day of technical sessions. A variety of 4W ORKSHOP P ROGRAM hors d 9oeuvres and a no-host bar will be available. Admittance to the reception is free to AAAI-06 registrants. A $40.00 per person fee ($10.00 for children) will be charged for spouses and other nontechni- cal conference registrants. AAAI-06 Poster & Demonstration Session A conference-wide poster and demonstra- tion session will be held on Wednesday, July 19, 5:30 3 9:30 PM and will feature AAAI-06 Technical Posters, Nectar Posters, AAAI Member Abstracts, Student Abstracts, Doctoral Consortium Abstracts, and Intelligent Systems Demonstrations. (For a complete listing of posters, please refer to page 14.) The accompanying re- ception will include a light dinner buffet and a no-host bar. Admittance to the re- ception is free to AAAI-06 registrants. A $30.00 per person fee ($10.00 for children) will be charged for spouses and other non- technical conference registrants. AAAI/SIGART Doctoral Consortium The Eleventh AAAI/SIGART Doctoral Consortium program will be held on Sun- day, July 16, 8:45 AM 3 5:30 PM , and Mon- day, July 17, 9:00 AM 3 5:40 PM in the Con- stitution Room on the mezzanine level of the Seaport Hotel. The Doctoral Consor- tium provides an opportunity for a group of Ph.D. students to discuss and explore their research interests and career objec- tives in an interdisciplinary workshop to- gether with a panel of established re- searchers. The thirteen students accepted to participate in this program, as well as several other DC-06 applicants, will par- ticipate in the Poster Session on Wednes- day evening. All interested AAAI-06 stu- dent registrants are invited to observe the presentations and participate in discus- sions at the workshop. AAAI and SIGART gratefully acknowledge grants from the National Science Foundation, Google Inc. and Microsoft that provide partial funding for this event. Student Blog & Forums AAAI06blog is a student run blog that will describe and document AAAI-06 and IAAI-06 from a student 9s perspective. A small group of student bloggers attending the conferences will post daily items at aaai06.blogspot.com describing their ob- servations, experiences, reactions, thoughts and questions. Pictures from the conference will be uploaded to the linked photo blog. Other students attending AAAI are welcome to participate by adding their own observations via com- ments attached to posts and photographs. In addition, several student-run forums are available via the AAAI-06 Student Ac- tivities website at pegasus2.isi.edu/aaai06- studentinfo/. Fifth Americas School on Agents and Multiagent Systems The Fifth Americas School on Agents and Multiagent Systems will be held July 14 - 17 at Harvard University and The Seaport All workshop participants must register for the AAAI-06 technical program and pay the supplemental workshop fee. Workshops will be held in the World Trade Center (WTC) and Seaport Hotel. All workshops are one full day unless noted otherwise. Sunday, July 16 W1: AI-Driven Technologies for Services-Oriented Com- puting. Organizers: Prashant Doshi, Richard Goodwin, and Amit Sheth. 8:45 AM 3 5:15 PM , Waterfront I, Harbor Level, WTC W4: Cognitive Robotics (1.5 days). Organizers: Michael Beetz, Kanna Rajan, Michael Thielscher, and Radu Bogdan Rusu. 8:30 AM 3 6:00 PM ,Sea- port A, Mezzanine Level. W5: Computational Aesthet- ics: Artificial Intelligence Approaches to Beauty and Happiness. Organizers: Hugo Liu and Rada Mihalcea. 8:45 AM 3 5:40 PM ,Cityview I, Upper Level, WTC W8: Event Extraction and Synthesis. Organizers: Naveen Ashish, Doug Appelt, Dayne Freitag, and Dmitry Zelenko. 9:15 AM 3 5:30 PM , North End Complex, Harbor Level, WTC W11: Intelligent Techniques for Web Personalization. Or- ganizers: Bamshad Mobasher and Sarabjot Singh Anand. Cambridge Complex, Harbor Level, WTC W12: Learning for Search. Organizers: Wheeler Ruml and Frank Hutter. 8:45 AM 3 6:00 PM ,Harborview II, Upper Lev- el, WTC W13: Modeling and Retrieval of Context (2 days). Organiz- ers: Thomas R. Roth-Berghofer, Stefan Schulz, and David B. Leake. 8:45 AM 3 6:00 p M ,Sea- port C, Mezzanine Level. Monday, July 17 W2: Auction-Based Robot Coordination. Organizers: Bernardine Dias, Sven Koenig and Michail G. Lagoudakis. 8:30 AM 3 6:00 PM ,Cityview I, Upper Level, WTC W3: Cognitive Modeling and Agent-Based Social Simula- tion. Organizers: M. Afzal Upal and Ron Sun. 1:50 PM 3 6:00 PM , Back Bay I, Mezzanine Level, WTC W4: Cognitive Robotics (Continued from Sunday), 8:30 AM 3 2:00 PM , Seaport A, Mez- zanine Level. W6: Educational Data Min- ing. Organizers: Joseph E. Beck, Esma Aimeur, and Tiffany Barnes. 8:30 AM 3 6:00 PM ,Sea- port B, Mezzanine Level. W7: Evaluation Methods for Machine Learning. Organiz- ers: Chris Drummond, William Elazmeh, and Nathalie Jap- kowicz. 9:00 AM 3 5:45 PM ,Back Bay II, Mezzanine Level, WTC W9: Heuristic Search, Mem- ory-Based Heuristics and Their Applications. Organiz- ers: Ariel Felner, Robert C. Holte, and Hector Geffner. 8:30 AM 3 5:45 PM ,Harborview II, Upper Level, WTC W10: Human Implications of Human-Robot Interac- tion. Organizer: Ted Metzler. 8:35 am 3 3:30 PM ,Waterfront I, Harbor Level, WTC W13: Modeling and Re- trieval of Context (Continued from Sunday). 9:15 AM 3 4:30 PM ,Seaport C, Mezzanine Lev- el W14: Modeling Others from Observations. Organizers: Gal Kaminka, David Pynadath, and Christopher Geib, 8:30 AM 3 1:15 PM ,Back Bay, Mezzanine Level, WTC W17: Statistical and Empiri- cal Approaches for Spoken Dialog Systems . Organizers: Pascal Poupart, Stephanie Sen- eff, Jason Williams, and Steve Young, 9:00 AM 3 5:30 PM ,Cam- bridge Complex, Harbor Level, WTC Thursday, July 20 The Mobile Robot Work- shop. Chair: Bob Avanzato. 10:00 AM 3 4:00 PM , Plaza A, Plaza Level, Seaport Hotel. Workshop Program C ONFERENCEATA G LANCE 5 MorningA FTERNOON E VENING Sunday, July 16 RegistrationRegistration Tutorial ForumTutorial Forum WorkshopsWorkshops AAAI/SIGART DCAAAI/SIGART DC Monday, July 17 RegistrationRegistrationOpening Reception Tutorial ForumTutorial Forum WorkshopsWorkshops AAAI/SIGART DCAAAI/SIGART DC AAAI Business Meeting Game Playing CompetititionGame Playing Competition Poker TournamentPoker Tournament Tuesday, July 18 RegistrationRegistration Fellows Panel AAAI-06 Keynote AddressIAAI-06 Invited Talk AAAI-06 & IAAI-06AAAI-06 & IAAI-06 Game Playing CompetitionGame Playing Competition Poker TournamentPoker Tournament Exhibits & RobotsExhibits & Robots Wednesday, July 19 RegistrationRegistrationPosters & IS Demos Invited TalksEngelmore Lectureand Reception AAAI-06 & IAAI 306AAAI-06 & IAAI 306 Game Playing CompetitionGame Playing Competition Poker TournamentPoker Tournament Exhibits & RobotsExhibits & RobotsRobot Finals Thursday, July 20 Registration AAAI-06 Invited TalksAAAI-06 / IAAI-06 ExhibitsRobot Workshop 6T UTORIAL F ORUM & I NVITED T ALKS Invited Talks & Panels All invited talks will be held in the World Trade Center. Tuesday, July 18 AAAI-06 Keynote Address AI and the Semantic Web Tim Berners-Lee (World Wide Web Consor- tium). Commonwealth Complex, Harbor Level, 9:00 3 10:00 AM (see page 3) IAAI-06 Invited Talk Winning the DARPA Grand Challenge Sebastian Thrun (Stanford University). Commonwealth Complex, Harbor Level, 1:50 3 2:50 PM The DARPA Grand Chal- lenge was the most signi[- cant event in the [eld of robotics in more than a decade. A mobile ground robot had to traverse 132 miles of punishing desert terrain in less than ten hours. In 2004, the best robot on- ly made 7.3 miles. A year later, Stanford won this historical challenge and cashed the $2M prize. This talk, delivered by the leader of the Stanford Racing Team, will provide insights into the software archi- tecture of Stanford 9s winning robot cStan- ley. d The robot heavily relied on advanced sensor technology, and advanced arti[cial intelligence to make sense out of the mas- sive amounts of sensor data acquired by the vehicle. The talk will introduce you into the fascinating world of autonomous robotics, share with you many of the race insights, and discuss with you some of the implications for the future of our society. AAAI Fellows 50th Anniversary Panel Commonwealth Complex, Harbor Level, 5:30 3 6:30 PM . Wednesday, July 19 AAAI-06 Invited Talk Developing an Intelligent Personal Assistant: The CALO Project Karen Myers, (SRI International). Amphi- theater, Mezzanine Level, 9:00 3 10:00 AM Knowledge workers today must juggle a range of tasks and responsibilities while maintaining awareness of deadlines, resources and events that could impact objectives. I will describe a collaboration by a team of 25 organizations to produce an intelligent personal assistant for im- proving the productivity of such workers. This assistant, called CALO (cognitive as- AAAI-06 technical registrants may at- tend up to four consecutive tutorials and receive one copy of the compre- hensive AAAI-06 Tutorial Forum Notes for an additional registration fee. Tutori- al attendees may redeem their tutorial syllabi tickets at the proceedings distri- bution area. All tutorials will be held in the World Trade Center. I: Sunday, July 16 9:00 AM 3 1:00 PM SA1: Auction-Based Agent Coordina- tion, M. Bernardine Dias, Gil Jones, Nidhi R. Kalra, Pinar Keskinocak, Sven Koenig, Michail G. Lagoudakis, and Robert Zlot (Cityview II, Upper Level) SA2: Case-Based Reasoning: Theory and Application, Cynthia Marling and William Cheetham (Harborview I, Upper Level) SA3: Computational Biology: Per- spective and Approaches Based on Feature Extraction and Selec- tion, Weixiong Zhang (Federal Com- plex, Mezzanine Level) 9:00 AM 3 6:00 PM SAP4: Getting the Most from Re- searchCyc, Larry Lefkowitz, Michael Witbrock, and Keith Goolsbey (Back Bay I, Mezzanine Level) SAP5: USARSim and MOAST: Ad- vanced Tools for High-Fidelity Simulation of Distributed Robot Systems, Stephen Balakirsky, Mike Lewis, and Stefano Carpin (Back Bay II, Mezzanine Level) II: Sunday, July 16 2:00 3 6:00 PM SP1: Constraint-Based Local Search, Laurent Michel and Pascal Van Hen- tenryck (Cityview II, Upper Level) SP2 : State-Space Traversal Tech- niques for AI Planning, Jussi Rin- tanen (Harborview I, Upper Level) SP3: Trading Agent Design and Anal- ysis, Michael P. Wellman (Federal Complex, Mezzanine Level) III: Monday, July 17 9:00 AM 3 1:00 PM MA1: The Art and Science of Action Programming Languages, Michael Thielscher (Cityview II, Upper Level) MA2: Scenario-based Design of User Interfaces: Theory from AI and Application in HCI, Hermann Kaindl (Harborview I, Upper Level) 9:00 AM 3 6:00 PM MAP3: Empirical Methods for ArtiL- cial Intelligence, Paul Cohen (North End Complex, Harbor Level) MAP4: Semantic Web Services, Michael Stollberg, Emilia Cimpian, Liliana Cabral, and John Domingue (Waterfront II, Harbor Level) MAP5: Temporal and Resource Rea- soning for Planning, Scheduling and Execution, Nicola Muscettola and Martha E. Pollack (Waterfront III, Harbor Level) IV: Monday, July 17 2:00 3 6:00 PM MP1: Intelligent User Interfaces: An Introduction, Mark T. Maybury (Cityview II, Upper Level) MP2: Language Independent Meth- ods of Clustering Similar Contexts (with applications), Ted Pedersen (Har- borview I, Upper Level) Tutorial Forum Hotel and World Trade Center. This pro- gram is aimed at orienting new graduate students in the [eld of Agents and Multi- agent Systems. The program will consists of two days of lectures by internationally recognized researchers in Agents and Multiagent Systems, followed by two days of AAAI-06 tutorials. The Americas Pro- gram Chairs are Roger Mailler, SRI Inter- national and David Sarne, Harvard Uni- versity. Sponsored by the International Foundation for Multiagent Systems (IF- MAS) and the American Association for Arti[cial Intelligence (AAAI). I NVITED T ALKS & S PECIAL M EETINGS 7 sistant that learns and organizes), both performs tasks on its user 9s behalf and as- sists with the [ltering, organization, and preparation of information. CALO is seed- ed with default problem-solving knowl- edge but learns to expand and improve its capabilities over time by observing and in- teracting with its user. AAAI-06 Invited Talk Global Inference and Learning: Towards Natural Language Understanding Dan Roth (University of Illinois at Urbana- Champaign). Cityview I, Upper Level, 9:00 3 10:00 AM The maturity of machine learning techniques allows us today to learn many low level natural language pred- icates and generate an ap- propriate vocabulary over which reasoning methods can be used to make signi[cant progress in natural lan- guage understanding. I will describe re- search on a framework that combines learning and inference. Our Inference with Classi[ers approach allows the out- put of local classi[ers for different prob- lem components to be assembled into a whole that re\ects global preferences and constraints. Examples will be drawn from cwh d attribution in natural language pro- cessing (determining who did what to whom when and where) and textual en- tailment (determining whether one utter- ance is a likely consequence of another). IAAI-06 Invited Talk Electrifying Knowledge Work: 362 In- novative Applications of ArtiLcial In- telligence 1989 3 2006 Neil Jacobstein (Teknowledge Corporation). Harborview II, Upper Level, 10:20 311:20 AM . Early stage arti[cial intelli- gence has already produced a wide range of valuable ap- plications in industry and government. Many of these applications have per- formed complex tasks such as planning, monitoring, design, risk assessment, diag- nosis, training, process control, classi[ca- tion, and analysis. AAAI 9s Innovative Ap- plications of AI Conference has published over 360 successful applications of AI in [elds as diverse as biotechnology, space \ight, manufacturing, security, paleontol- ogy, construction, energy, music, mili- tary, intelligence, banking, telecommuni- cations, news media, management, law, emergency services, agriculture, treaty veri[cation, and many others. This talk will review the patterns that connect these applications over 18 years of the IAAI conference: what worked, what did- n 9t, and what were the key trends. None of these systems exhibited general intelli- gence, but each documented our ability to codify and distribute human problem solving knowledge, and put it to work. Robert S. Engelmore Memorial Lecture What Do We Know About Knowledge? Bruce G. Buchanan (University Professor of Computer Science Emeritus, University of Pittsburgh). Harborview II, Upper Level, 4:20 3 5:20 PM Intelligent systems need knowledge. However, the simple equation cknowl- edge is power d leaves three major questions unan- swered. First what do we mean by cknowledge, d second, what do we mean by cpower, d and third, what do we mean by cis? d In this talk Buchanan will examine these questions. In particu- lar he will focus on some of the mile- stones in understanding the nature of knowledge and some of what we have learned from [fty years of AI. The disci- pline and detail required to write pro- grams that use knowledge have given us some valuable lessons for implementing the knowledge principle. But there are still interesting challenges ahead. Thursday, July 20 AAAI-06 Invited Talk Unifying Logical and Statistical AI Pedro Domingos (University of Washington). Amphitheater, Mezzanine Level, 9:00 3 10:00 AM Intelligent agents must be able to handle the complex- ity and uncertainty of the real world. Logical AI has focused mainly on the for- mer, and statistical AI on the latter. Markov logic combines the two by attaching weights to [rst-order formu- las and viewing them as templates for fea- tures of Markov networks. Inference algo- rithms for Markov logic draw on ideas from satis[ability, Markov chain Monte Carlo and knowledge-based model con- struction. Learning algorithms are based on the voted perceptron and inductive logic programming. Markov logic has been successfully applied to problems in entity resolution, link prediction, infor- mation extraction and others, and is the basis of the open-source Alchemy system. AAAI-06 Invited Talk Cognitive Tutors and Opportunities for Convergence of Human and Ma- chine Learning Theory Ken Koedinger (Carnegie Mellon University). Cityview I, Upper Level, 9:00 3 10:00 AM . Cognitive tutors are com- puter-based intelligent tu- tors that are based on cog- nitive psychology theory and employ arti[cial intel- ligence methods. Cognitive tutors have led to signi[cant improve- ments in student learning and are now in regular use in mathematics classrooms in over 2,000 schools across the country. They have also been an important basic research vehicle to test and advance both psychology and AI theory. Besides illus- trating this important application of AI, I will also discuss how we have diverged from a time when theoretical explorations of machine and human learning were more closely aligned and how it is now time reconvene and to fruitfully compare and contrast the independent theoretical advances both [elds have made. Special Meetings AAAI Business Meeting The AAAI Annual Business Meeting will be held Monday, July 17, 12:45 3 1:15 pm, Seaport B, Seaport Hotel AAAI Conference Committee Meeting The Conference Committee Meeting will be held Thursday, July 19, 7:45 3 8:45 AM ,16th Floor Boardroom, Seaport Hotel AAAI Publications Committee Meeting The Publications Committee Meeting will be held Wednesday, July 19, 12:30 3 1:50 PM , Aura Restaurant, Seaport Hotel AI Magazine Editorial Board Meeting The AI Magazine Editorial Board Meet- ing will be held Tuesday, July 18, 12:30 3 2:00 PM ,16th Floor Boardroom, Seaport Hotel Executive Council Meeting The AAAI Executive Council Meeting will be held Monday, July 17, 9:00 am 3 5:00 PM ,16th Floor Boardroom, Seaport Hotel. Continental breakfast will be available at 8:30 AM . Strategic Planning Committee Meeting The AAAI Strategic Planning Committee Meeting will be held Wednesday, July 19, 7:30 3 9:00 AM ,16th Floor Board- room, Seaport Hotel. 8C ONFERENCE S CHEDULE 4T UESDAY J ULY 18 Seaport B&C Harborview I (WTC) Cityview II (WTC) 8:30 - 9:00 AM: AAAI-06 Welcome and Opening Remarks and Paper Award Presentations, Yolanda Gil and Raymond Mooney, Commonwealth Complex, Harbor Level, WTC IAAI-06 Welcome, Robert S. Engelmore Memorial Award, and Deployed Application Award Announcements, Bruce Porter, William Cheetham and David B. Leake AAAI Special Award Presentations, Ron Brachman and Alan Mackworth, Commonwealth Complex, Harbor Level, WTC 9:00 - 10:00 AM: AAAI-06 Keynote Address: AI and the Semantic Web, Tim Berners-Lee; Introduction by Yolanda Gil, Commonwealth Complex, Harbor Level, WTC 10:20 3 11:20 AM Plenary Machine Learning I Chair: Weixiong Zhang Active Learning with Near Misses, Nela Gurevich, Shaul Markovitch, and Ehud Rivlin Senior: Towards Chemical Universal Turing Machines, Stephen Muggleton Nectar: Activity-Centric Email: A Machine Learning Ap- proach, Nicholas Kushmerick, Tessa Lau, Mark Dredze, and Rinat Khoussainov Multiagent Systems I Chair: Shlomo Zilberstein Analysis of Privacy Loss in Distributed Constraint Opti- mization, Rachel Greenstadt, Jonathan P. Pearce, and Milind Tambe A New Approach to Distributed Task Assignment using Lagrangian Decomposition and Distributed Constraint Satisfaction, Katsutoshi Hirayama Algorithms for Rationalizability and CURB Sets, Michael Benisch, George Davis, and Tuomas Sandholm Planning Chair: Jussi Rintanen Senior: Deconstructing Planning as Satis[ability, Henry Kautz Factored Planning: How, When, and When Not, Ronen I. Brafman and Carmel Domshlak A Modular Action Description Language, Vladimir Lifs- chitz and Wanwan Ren 11:30 3 12:30 PM Machine Learning II Chair: Rich Caruana An Ef[cient Algorithm for Local Distance Metric Learn- ing, Liu Yang, Rong Jin, Rahul Sukthankar, and Yi Liu Ef[cient L 1 Regularized Logistic Regression, Su-In Lee, Honglak Lee, Pieter Abbeel, and Andrew Y. Ng Senior: Knowledge Infusion, Leslie G. Valiant Multiagent Systems II Chair: Jeff Rosenschein Overlapping Coalition Formation for Ef[cient Data Fu- sion in Multi-Sensor Networks, Viet Dung Dang, Rajdeep K. Dash, Alex Rogers, and Nicholas R. Jennings Multiparty Proactive Communication: A Perspective for Evolving Shared Mental Models, Kaivan Kamali, Xiao- cong Fan, and John Yen From Centralized to Distributed Selective Overhearing, Gery Gutnik and Gal A. Kaminka Planning: Plan Recognition Chair: Sven Koenig Sensor-Based Understanding of Daily Life via Large- Scale Use of Common Sense, William Pentney, Ana- Maria Popescu, Shiaokai Wang, Henry Kautz, and Matthai Philipose Fast Hierarchical Goal Schema Recognition, Nate Blay- lock and James Allen Reasoning about Partially Observed Actions, Megan Nance, Adam Vogel, and Eyal Amir 1:50 3 2:50 PM Machine Learning: Case-Based Reasoning and Analogy Chair: David Aha Nectar: Progress in Textual Case-Based Reasoning: Pre- dicting the Outcome of Legal Cases from Text, Stefanie Brüninghaus and Kevin D. Ashley Nectar: Optimizing Similarity Assessment in Case-Based Reasoning, Armin Stahl and Thomas Gabel Strategy Variations in Analogical Problem Solving, Tom Y. Ouyang and Kenneth D. Forbus Human Computer Interaction & Cognitive Modeling: Life-Like Characters & Music Chair: Bryan Loyall Using Anticipation to Create Believable Behavior, Carlos Martinho and Ana Paiva Senior: Virtual Humans, William R. Swartout Nectar: TempoExpress: An Expressivity-Preserving Musi- cal Tempo Transformation System, Maarten Grachten, Josep-Lluís Arcos, and Ramon López de Mántaras Planning: Robust Planning Chair: David E. Wilkins Contingent Planning with Goal Preferences, Dmitry Shaparau, Marco Pistore, and Paolo Traverso Exploration of the Robustness of Plans, Maria Fox, Richard Howey, and Derek Long Robust Execution on Contingent, Temporally Flexible Plans, Stephen A. Block, Andreas F. Wehowsky, and Brian C. Williams 3:00 3 4:00 PM Machine Learning: Decision Trees & Association Rules Chair: Robert C. Holte Minimum Description Length Principle: Generators Are Preferable to Closed Patterns, Jinyan Li, Haiquan Li, Limsoon Wong, Jian Pei, and Guozhu Dong Nectar: When a Decision Tree Learner Has Plenty of Time, Saher Esmeir and Shaul Markovitch Anytime Induction of Decision Trees: An Iterative Im- provement Approach, Saher Esmeir and Shaul Markovitch Human Computer Interaction & Cognitive Modeling: Intelligent User Interfaces Chair: Jon Herlocker Evaluating Preference-based Search Tools: A Tale of Two Approaches, Paolo Viappiani, Boi Faltings, and Pearl Pu Extracting Knowledge about Users 9 Activities from Raw Workstation Contents, Tom M. Mitchell, Sophie H. Wang, Yifen Huang, and Adam Cheyer Nectar: Lessons on Applying Automated Recommender Systems to Information-Seeking Tasks, Joseph A. Kon- stan, Sean M. McNee, Cai-Nicolas Ziegler, Roberto Torres, Nishikant Kapoor, and John T. Riedl Planning under Uncertainty Chair: David E. Smith Compiling Uncertainty Away: Solving Conformant Planning Problems using a Classical Planner (Some- times), Héctor Palacios and Héctor Geffner Probabilistic Temporal Planning with Uncertain Dura- tions, Mausam and Daniel S. Weld PPCP: Ef[cient Probabilistic Planning with Clear Pref- erences in Partially-Known Environments, Maxim Likhachev and Anthony Stentz 4:20 3 5:20 PM Machine Learning: Dimensionality Reduction Chair: Weixiong Zhang Tensor Embedding Methods, Guang Dai and Dit-Yan Ye- ung Nectar: Embedding Heterogeneous Data Using Statistical Models, Amir Globerson, Gal Chechik, Fernando Pereira, and Naftali Tishby Nectar: An Introduction to Nonlinear Dimensionality Reduction by Maximum Variance Unfolding, Kilian Q. Weinberger and Lawrence K. Saul Model-Based Systems Chair: Johan de Kleer A Causal Analysis Method for Concurrent Hybrid Au- tomata, Michael W. Hofbaur and Franz Wotawa Approximate Compilation for Embedded Model-based Reasoning, Barry O 9Sullivan and Gregory M. Provan A Two-Step Hierarchical Algorithm for Model-Based Di- agnosis, Alexander Feldman and Arjan van Gemund Perception & Cognition Chair: Benjamin Kuipers Self-Supervised Acquisition of Vowels in American En- glish, Michael H. Coen Senior: Multimodal Cognitive Architecture: Making Per- ception More Central to Intelligent Behavior, B. Chan- drasekaran Nectar: Laughing with HAHAcronym, a Computational Humor System, Oliviero Stock and Carlo Strapparava Evening Panel Presentation 5:30 36:30 PM AAAI Fellows 50th Anniversary Panel Commonwealth Complex, World Trade Center C ONFERENCE S CHEDULE 4T UESDAY , J ULY 189 Coffee breaks will be held at 10:00 3 10:20 AM and 4:00 3 4:20 PM . The lunch break will be held from 12:30 3 1:50 PM . Seaport A Cityview I (WTC) Harborview II (IAAI) Natural Language I Chair: Shaul Markovitch Corpus-based and Knowledge-based Measures of Text Se- mantic Similarity, Rada Mihalcea, Courtney Corley, and Carlo Strapparava Learning Noun-Modi[er Semantic Relations with Corpus- based and WordNet-based Features, Vivi Nastase, Jelber Sayyad-Shirabad, Marina Sokolova, and Stan Szpakowicz Negation, Contrast and Contradiction in Text Processing, Sanda Harabagiu, Andrew Hickl, and Finley Lacatusu AI & the Web: Collaborative Filtering Chair: Sofus Macskassy Model-Based Collaborative Filtering as a Defense against Pro[le Injection Attacks, Bamshad Mobasher, Robin Burke, and J. J. Sandvig Bookmark Hierarchies and Collaborative Recommenda- tion, Ben Markines, Lubomira Stoilova, and Filippo Menczer Mixed Collaborative and Content-Based Filtering with Us- er-Contributed Semantic Features, Matthew Garden and Gregory Dudek IAAI-06: Knowledge-Based Systems Chair: Neil Jacobstein Deployed Application :Case-Based Reasoning for General Electric Appliance Customer Support, William Cheetham Emerging Application: Heuristic Search and Information Visualization Methods for School Redistricting, Marie des- Jardins, Blazej Bulka, Ryan Carr, Andrew Hunt, Priyang Rathod, and Penny Rheingans Natural Language II Chair: Dayne B. Freitag Nectar: Opinion Extraction and Summarization on the Web, Minqing Hu and Bing Liu Proposing a New Term Weighting Scheme for Text Catego- rization, Man Lan, Chew-Lim Tan, and Hwee-Boon Low Nectar: Beyond Bags of Words: Modeling Implicit User Preferences in Information Retrieval, Donald Metzler and W. Bruce Croft AI & the Web: Trust & Security Chair: Biplav Srivastava Trust Representation and Aggregation in a Distributed Agent System, Yonghong Wang and Munindar P. Singh Social Network-based Trust in Prioritized Default Logic, Yarden Katz and Jennifer Golbeck Using Semantic Web Technologies for Policy Management on the Web, Lalana Kagal, Tim Berners-Lee, Dan Connolly, and Daniel Weitzner IAAI-06: Data Mining Chair: Ted Senator Deployed Application :Predicting Electricity Distribution Feeder Failures Using Machine Learning Susceptibility Analysis, Philip Gross, Albert Boulanger, Marta Arias, David Waltz, Philip M. Long, Charles Lawson, Roger Anderson, Matthew Koenig, Mark Mastrocinque, William Fairechio, John A. Johnson, Serena Lee, Frank Doherty, and Arthur Kressner Emerging Application: A Sequential Covering Evolutionary Algorithm for Expressive Music Performance, Rafael Ramirez, Amaury Hazan, Jordi Mariner, and Esteban Maestre Natural Language III Chair: Ted Pedersen Senior: Machine Reading, Oren Etzioni, Michele Banko, and Michael J. Cafarella Nectar: A Look at Parsing and Its Applications, Matthew Lease, Eugene Charniak, Mark Johnson, and David McClosky Societal Grounding Is Essential to Meaningful Language Use, David DeVault, Iris Oved, and Matthew Stone AI & the Web: Ontologies Chair: Vinay K. Chaudhri OntoSearch: A Full-Text Search Engine for the Semantic Web, Xing Jiang and Ah-Hwee Tan Towards Modeling Threaded Discussions using Induced Ontology Knowledge, Donghui Feng, Jihie Kim, Erin Shaw, and Eduard Hovy Inexact Matching of Ontology Graphs Using Expectation- Maximization, Prashant Doshi and Christopher Thomas IAAI-06 Invited Talk Winning the DARPA Grand Challenge, Sebastian Thrun, introduced by Bruce Porter Commonwealth Complex, WTC Knowledge-Based Systems Chair: Michael Witbrock Merging Strati[ed Knowledge Bases under Constraints, Guilin Qi, Weiru Liu, and David A. Bell Nectar: Large Scale Knowledge Base Systems: An Empiri- cal Evaluation Perspective, Yuanbo Guo, Abir Qasem, and Jeff HeZin A Uni[ed Knowledge Based Approach for Sense Disam- biguation and Semantic Role Labeling, Peter Z. Yeh, Bruce Porter, and Ken Barker AI & the Web: Using the Web as a Knowledge Source Chair: Brian Milch Overcoming the Brittleness Bottleneck using Wikipedia: Enhancing Text Categorization with Encyclopedic Knowl- edge, Evgeniy Gabrilovich and Shaul Markovitch WikiRelate! Computing Semantic Relatedness Using Wikipedia, Michael Strube and Simone Paolo Ponzetto Organizing and Searching the World Wide Web of Facts - Step One: The One-Million Fact Extraction Challenge, Marius Pasca, Dekang Lin, Jeffrey Bigham, Andrei Lifchits, and Alpa Jain IAAI-06: Biomedical Applications 1 Chair: Elaine Rich Emerging Application: Visual Explanation of Evidence with Additive Classi[ers, Brett Poulin, Roman Eisner, Duane Szafron, Paul Lu, Russ Greiner, D. S. Wishart, Alona Fyshe, Brandon Pearcy, Cam MacDowell , and John Anvik Emerging Application: MedEthEx: A Prototype Medical Ethics Advisor, Michael Anderson, Susan Leigh Anderson, and Chris Armen Information Integration Chair: Eyal Amir Compilation of Query-Rewriting Problems into Tractable Fragments of Propositional Logic, Yolifé Arvelo, Blai Bonet, and María Esther Vidal Nectar: Supporting Queries with Imprecise Constraints, Ul- las Nambiar and Subbarao Kambhampati Classi[cation Spanning Private Databases, Ke Wang, Yabo Xu, Rong She, and Philip S. Yu AI & the Web: Information Extraction Chair: Sofus Macskassy Table Extraction Using Spatial Reasoning on the CSS2 Vi- sual Box Model, Wolfgang Gatterbauer and Paul Bohunsky Mining Comparative Sentences and Relations, Nitin Jindal and Bing Liu Nectar: Overview of AutoFeed: An Unsupervised Learning System for Generating Webfeeds, Bora Gazen and Steven Minton IAAI-06: Software Agents Chair: Bill Cheetham Emerging Application: Building Explainable Arti[cial Intel- ligence Systems, Mark G. Core, H. Chad Lane, Michael van Lent, Dave Gomboc, Steve Solomon, and Milton Rosenberg Emerging Application: Local Negotiation in Cellular Net- works: From Theory to Practice, Raz Lin, Daphna Dor- Shifer, Sarit Kraus, and David Sarne 10C ONFERENCE S CHEDULE 4W EDNESDAY , J ULY 19 Seaport B&C Harborview I (WTC) Cityview II (WTC) AAAI-06 Invited Talk Session 9:00 - 10:00 AM: Developing an Intelligent Personal Assistant: The CALO Project , Karen Myers, Introduced by Martha E. Pollack, Amphitheater, Mezzanine Level 9:00 - 10:00 AM: Global Inference and Learning: Towards Natural Language Understanding , Dan Roth, Introduced by Leslie Valiant, Cityview I, World Trade Center 10:20 3 11:20 AM Machine Learning: Reinforcement Learning I Chair: Shimon Whiteson Mixtures of Predictive Linear Gaussian Models for Non- linear, Stochastic Dynamical Systems, David Wingate and Satinder Singh Representing Systems with Hidden State, Christopher Hundt, Prakash Panagaden,Joelle Pineau, and Doina Pre- cup Decision Tree Methods for Finding Reusable MDP Ho- momorphisms, Alicia Peregrin Wolfe and Andrew G. Barto Knowledge Representation I Chair: Michael Thielscher Towards an Axiom System for Default Logic, Gerhard Lakemeyer and Hector J. Levesque Forgetting and Con\ict Resolving in Disjunctive Logic Programming, Thomas Eiter and Kewen Wang Finding Maximally Satis[able Terminologies for the De- scription Logic ALC, Thomas Meyer, Kevin Lee, Richard Booth, and Jeff Z. Pan Constraint Satisfaction I Chair: Abdul Sattar Temporal Preference Optimization as Weighted Con- straint Satisfaction, Michael D. MofYtt and Martha E. Pollack Simple Randomized Algorithms for Tractable Row and Tree Convex Constraints, T. K. Satish Kumar Length-Lex Ordering for Set CSPs, Carmen Gervet and Pascal van Hentenryck 11:30 3 12:30 PM Machine Learning: Reinforcement Learning II Chair: Pascal Poupart Optimal Unbiased Estimators for Evaluating Agent Per- formance, Martin Zinkevich, Michael Bowling, Nolan Bard, Morgan Kan, and Darse Billings Nectar: Real-Time Evolution of Neural Networks in the NERO Video Game, Kenneth O. Stanley, Bobby D. Bryant, Igor Karpov, and Risto Miikkulainen Sample-Ef[cient Evolutionary Function Approximation for Reinforcement Learning, Shimon Whiteson and Peter Stone Knowledge Representation II Chair: Xiaoqin (Shelley) Zhang Explaining Qualitative Decision under Uncertainty by Argumentation, Leila Amgoud and Henri Prade On the Complexity of Linking Deductive and Abstract Argument Systems, Michael Wooldridge, Paul E. Dunne, and Simon Parsons Model-Checking Memory Requirements of Resource- Bounded Reasoners, Alexandre Albore, Natasha Alechina, Piergiorgio Bertoli, Chiara Ghidini, Brian Logan, and Lu- ciano SeraYni Constraint Satisfaction II Chair: Barry O 9Sullivan Exploiting Tree Decomposition and Soft Local Consis- tency In Weighted CSP, Simon de Givry, Thomas Schiex, and Gérard Verfaillie Weighted Constraint Satisfaction with Set Variables, J. H. M. Lee and C. F. K. Siu An Ef[cient Way of Breaking Value Symmetries, Jean- François Puget 1:50 3 2:50 PM Machine Learning: Transfer Learning Chair: Rich Maclin Cross-Domain Knowledge Transfer Using Structured Representations, Samarth Swarup and Sylvian R. Ray Using Homomorphisms to Transfer Options across Con- tinuous Reinforcement Learning Domains, Vishal Soni and Satinder Singh Value-Function-Based Transfer for Reinforcement Learn- ing Using Structure Mapping, Yaxin Liu and Peter Stone Game Theory I Chair: Amy Greenwald Senior: Methods for Empirical Game-Theoretic Analysis, Michael P. Wellman Impersonation-Based Mechanisms, Moshe Babaioff, Ron Lavi, and Elan Pavlov Strong Mediated Equilibrium, Dov Monderer and Moshe Tennenholtz Markov Decision Processes Chair: Judy Goldsmith Compact, Convex Upper Bound Iteration for Approxi- mate POMDP Planning, Tao Wang, Pascal Poupart, Michael Bowling, and Dale Schuurmans Point-based Dynamic Programming for DEC-POMDPs, Daniel Szer and François Charpillet On the Dif[culty of Achieving Equilibrium in Interac- tive POMDPs, P rashant Doshi and Piotr J. Gmytrasiewicz 3:00 3 4:00 PM Machine Learning: SVM Learning & Kernels Chair: Shaul Markovitch A Simple and Effective Method for Incorporating Advice into Kernel Methods, Richard Maclin, Jude Shavlik, Trevor Walker, and Lisa Torrey Robust Support Vector Machine Training via Convex Outlier Ablation, Linli Xu, Koby Crammer, and Dale Schuurmans kFOIL: Learning Simple Relational Kernels, Niels Landwehr, Andrea Passerini, Luc De Raedt, and Paolo Frasconi Game Theory II Chair: Kevin Leyton-Brown Nonexistence of Voting Rules That Are Usually Hard to Manipulate, Vincent Conitzer and Tuomas Sandholm Robust Mechanisms for Information Elicitation, Aviv Zo- har and Jeffrey S. Rosenschein The Complexity of Bribery in Elections, Piotr Faliszews- ki, Edith Hemaspaandra, and Lane A. Hemaspaandra Constraint Satisfaction III Chair: Toby Walsh Senior: Constraints: The Ties that Bind, Eugene C. Freuder Local-Search techniques for Boolean Combinations of Pseudo-Boolean Constraints, Lengning Liu and Miroslaw Truszczynski A Quadratic Propagator for the Inter-Distance Con- straint, Claude-Guy Quimper, Alejandro López-Ortiz, and Gilles Pesant 4:20 3 5:20 PM Machine Learning: Unsupervised & Semi- Supervised Learning Chair: Chris Drummond Clustering by Exceptions, Fabrizio Angiulli Learning Systems of Concepts with an In[nite Relation- al Model, Charles Kemp, Joshua B. Tenenbaum, Thomas L. GrifYths, Takeshi Yamada, and Naonori Ueda Semi-supervised Multi-label Learning by Constrained Non-negative Matrix Factorization, Yi Liu, Rong Jin, and Liu Yang Game Theory III Chair: Makoto Yokoo A Computational Model of Logic-Based Negotiation, Dongmo Zhang and Yan Zhang Regret-based Incremental Partial Revelation Mecha- nisms, Nathanaël HyaYl and Craig Boutilier Nectar: Handling Self-Interest in Groups, with Minimal Cost, Ruggiero Cavallo Constraint Satisfaction IV Chair: Jimmy H. M. Lee Improved Bounds for Computing Kemeny Rankings, Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam The Impact of Balancing on Problem Hardness in a Highly Structured Domain , Carlos Ansótegui, Ramón Bé- jar, César Fernàndez, Carla Gomes, and Carles Mateu A BDD-Based Polytime Algorithm for Cost-Bounded In- teractive Con[guration, Tarik Hadzic and Henrik Reif Andersen Evening AAAI-06 Technical Posters & Intelligent Systems Demonstrations 5:30 39:30 PM Plaza Ballroom, Plaza Level, Seaport (Posters listed on page 14) Talks C ONFERENCE S CHEDULE 4W EDNESDAY , J ULY 1911 Coffee breaks will be held at 10:00-10:20 AM and 4:00 3 4:20 PM . The lunch break will be held from 12:30 3 1:50 PM . Seaport A Cityview I (WTC) Harborview II (IAAI) Search: Games I Chair: Vincent Conitzer Overcon[dence or Paranoia? Search in Imperfect-Informa- tion Games, Austin Parker, Dana Nau, and VS Subrahmani- an Properties of Forward Pruning in Game-Tree Search, Yew Jin Lim and Wee Sun Lee RankCut 4 A Domain Independent Forward Pruning Method for Games, Yew Jin Lim and Wee Sun Lee AI & the Web: Information Retrieval Chair: Jon Herlocker Minimally Invasive Randomization fro Collecting Unbi- ased Preferences from Clickthrough Logs, Filip Radlinski and Thorsten Joachims Predicting Task-Speci[c Webpages for Revisiting, Arwen Twinkle Lettkeman, Simone Stumpf, Jed Irvine, and Jonathan Herlocker Improve Web Search Using Image Snippets, Xiao-Bing Xue, Zhi-Hua Zhou, and Zhongfei (Mark) Zhang IAAI-06 Invited Talk Electrifying Knowledge Work: 362 Innovative Appli- cations of ArtiLcial Intelligence 1989-2006, Neil Jacob- stein, introduced by Bill Cheetham Search: Games II Chair: Makoto Yokoo Prob-Max n : Playing N-Player Games with Opponent Mod- els, Nathan Sturtevant, Martin Zinkevich, and Michael Bowl- ing On Strictly Competitive Multi-Player Games, Felix Brandt, Felix Fischer, and Yoav Shoham A Polynomial-Time Algorithm for Action Graph Games, Albert Xin Jiang and Kevin Leyton-Brown AI & the Web: Information Interaction Chair: Tony Cohn Using Semantics to Identify Web Objects, Nathanael Chambers, James Allen, Lucian Galescu, Hyuckchul Jung, and William Taysom Automatically Labeling the Inputs and Outputs of Web Services, Kristina Lerman, Anon Plangprasopchok, and Craig A. Knoblock Spinning Multiple Social Networks for Semantic Web, Yu- taka Matsuo, Masahiro Hamasaki, Yoshiyuki Nakamura, Takuichi Nishimura, Kôiti Hasida, Hideaki Takeda, Junichiro Mori, Danushka Bollegala, and Mitsuru Ishizuka IAAI-06: Biomedical Applications 2 Chair: Howard Shrobe Emerging Application: CM-Extractor: An Application for Automating Medical Quality Measures Abstraction in a Hospital Setting, Mark L. Morsch, Joel L. Vengco, Ronald E. Sheffer, Jr., and Daniel T. Heinze Emerging Application: Monitoring Food Safety by Detecting Patterns in Consumer Complaints, Artur Dubrawski, Kim- berly Elenberg, Andrew Moore, and Maheshkumar Sabhnani Search: Games & Applications Chair: Vincent Conitzer An Ef[cient Algorithm for Scatter Chart Labeling , Sebas- tian Theophil and Arno Schödl Monte Carlo Go Has a Way to Go, Haruhiro Yoshimoto, Kazuki Yoshizoe, Tomoyuki Kaneko, Akihiro Kishimoto, and Kenjiro Taura A Competitive Texas Hold 9em Poker Player via Automated Abstraction and Real-Time Equilibrium Computation, An- drew Gilpin and Tuomas Sandholm IIC: Agent Architectures Chair: Karen Myers A Uni[ed Cognitive Architecture for Physical Agents, Pat Langley and Dongkyu Choi TacTex-05: A Champion Supply Chain Management Agent, David Pardoe and Peter Stone QUICR-Learning for Multi-Agent Coordination, Adrian K. Agogino and Kagan Tumer IAAI-06: Constraint-Based Systems Chair: Bruce Porter Deployed Application :Constraint-Based Random Stimuli Generation for Hardware Veri[cation, Yehuda Naveh, Michal Rimon, Itai Jaeger, Yoav Katz, Michael Vinov, Eitan Marcus, and Gil Shurek Emerging Application: AWDRAT: A Cognitive Middleware System for Information Survivability, Howard Shrobe, Robert Laddaga, Bob Balzer, Neil Goldman, Dave Wile, Marcelo Tallis, Tim Hollebeek, and Alexander Egyed Search I Chair: Vadim Bulitko Estimating Search Tree Size, Philip Kilby, John Slaney, Sylvie Thiébaux, and Toby Walsh Planning with First-Order Temporally Extended Goals us- ing Heuristic Search, Jorge A. Baier and Sheila A. McIlraith Dual Search in Permutation State Spaces, Uzi Zahavi, Ariel Felner, Robert Holte, and Jonathan Schaeffer IIC: Integrated Natural Language Processing Chair: Candy Sidner Deeper Natural Language Processing for Evaluating Stu- dent Answers in Intelligent Tutoring Systems, Vasile Rus and Art C. Graesser Walk the Talk: Connecting Language, Knowledge, and Ac- tion in Route Instructions, Matt MacMahon, Brian Stankiewicz, and Benjamin Kuipers Integrating Joint Intention Theory, Belief Reasoning, and Communicative Action for Generating Team-Oriented Dia- logue, Rajah Annamalai Subramanian, Sanjeev Kumar, and Philip Cohen IAAI-06: Knowledge-Based Systems 2 Chair: Karen Haigh Deployed Application :Machine Translation for Manufactur- ing: A Case Study at Ford Motor Company, Nestor Rychty- ckyj Emerging Application: Ontology Based Semantic Modeling for Chinese Ancient Architectures, Y ong Liu, Congfu Xu, Qiong Zhang, and Yunhe Pan Search II Chair: Yaxin Liu DD* Lite: Ef[cient Incremental Search with State Domi- nance, G. Ayorkor Mills-Tettey, Anthony Stentz, and M. Bernardine Dias Domain-Independent Structured Duplicate Detection, Rong Zhou and Eric A. Hansen Nectar: A Breadth-First Approach to Memory-Ef[cient Graph Search, Rong Zhou and Eric A. Hansen IIC: Human-Robot Interaction Chair: Candy Sidner Perspective Taking: An Organizing Principle for Learning in Human-Robot Interaction, Matt Berlin, Jesse Gray, An- drea L. Thomaz, and Cynthia Breazeal Intuitive linguistic Joint Object Reference in Human- Robot Interaction: Human Spatial Reference Systems and Function-Based Categorization for Symbol Grounding, Reinhard Moratz Know Thine Enemy: A Champion RoboCup Coach Agent, Gregory Kuhlmann, William B. Knox, and Peter Stone IAAI-06: Robert S. Engelmore Memorial Lecture What Do We Know About Knowledge? Bruce G. Buchanan , introduced by David Leake 12C ONFERENCE S CHEDULE 4T HURSDAY , J ULY 20 Seaport B&C Harborview I (WTC) Cityview II (WTC) 9:00 3 10:00 AM AAAI-06 Invited Talk Session Unifying Logical and Statistical AI Pedro Domingos, Introduced by Tom Mitchell Amphitheater, World Trade Center Cognitive Tutors and Opportunities for Convergence of Human and Machine Learning Theory Ken Koedinger, Introduced by Kenneth Forbus Cityview I, World Trade Center 10:20 3 11:20 AM Machine Learning: Statistical Relational Learning Chair: Brian Milch Sound and Ef[cient Inference with Probabilistic and Deterministic Dependencies, Hoifung Poon and Pedro Domingos Memory-Ef[cient Inference in Relational Domains, Parag Singla and Pedro Domingos Identi[cation and Evaluation of Weak Community Structures in Networks, Jianhua Ruan and Weixiong Zhang Logic Programming Chair: Vladimir Lifschitz Elementary Sets of Logic Programs, Martin Gebser, Joohyung Lee, and Yuliya Lierler Answer Sets for Logic Programs with Arbitrary Abstract Constraint Atoms, Tran Cao Son, Enrico Pontelli, and Phan Huy Tu Bounded Treewidth as a Key to Tractability of Knowl- edge Representation and Reasoning, Georg Gottlob, Rein- hard Pichler, and Fang Wei Temporal Reasoning Chair: Yves Lesperance Optimal Scheduling of Contract Algorithms for Any- time Problems, Alejandro López-Ortiz, Spyros Angelopou- los, and Angèle M. Hamel Tractable Classes of Metric Temporal Problems with Domain Rules, T. K. Satish Kumar Learning Partially Observable Action Schemas, Dafna Shahaf and Eyal Amir 11:30 3 12:30 PM Machine Learning: Evolutionary Computation Chair: Shimon Whiteson A New Approach to Estimating the Expected First Hit- ting Time of Evolutionary Algorithms, Yang Yu and Zhi- Hua Zhou Con\ict Resolution and a Framework for Collaborative Interactive Evolution, Sean R. Szumlanski, Annie S. Wu, and Charles E. Hughes A Direct Evolutionary Feature Extraction Algorithm for Classifying High Dimensional Data, Qijun Zhao, David Zhang, and Hongtao Lu UAI: Decision Theory Chair: Judy Goldsmith Ef[cient Active Fusion for Decision-Making via VOI Ap- proximation, Wenhui Liao and Qiang Ji CUI Networks: A Graphical Representation for Condi- tional Utility Independence, Yagil Engel and Michael P. Wellman Nectar: Preference Elicitation and Generalized Additive Utility, Darius Braziunas and Craig Boutilier SatisLability I Chair: Miroslav Velev On the Use of Partially Ordered Decision Graphs in Knowledge Compilation and Quanti[ed Boolean For- mulae, Hélène Fargier and Pierre Marquis Model Counting: A New Strategy for Obtaining Good Bounds, Carla P. Gomes, Ashish Sabharwal, and Bart Sel- man Nectar: Acquiring Constraint Networks Using a SAT- based Version Space Algorithm, Christian Bessiere, Remi Coletta, Frédéric Koriche, and Barry O 9Sullivan 1:50 3 2:50 PM Machine Learning: Ensemble Learning Chair: Dragos D. Margineantu On Combining Multiple Classi[ers Using an Evidential Approach, Yaxin Bi, Sally McClean, and Terry Anderson Boosting Expert Ensembles for Rapid Concept Recall, Achim Rettinger, Martin Zinkevich, and Michael Bowling Gradient Boosting for Sequence Alignment, Charles Parker, Alan Fern, and Prasad Tadepalli UAI: Probabilistic Inference Chair: Richard Korf MPE and Partial Inversion in Lifted Probabilistic Vari- able Elimination, Rodrigo de Salvo Braz, Eyal Amir, and Dan Roth Solving MAP Exactly by Searching on Compiled Arith- metic Circuits, Jinbo Huang, Mark Chavira, and Adnan Darwiche An Edge Deletion Semantics for Belief Propagation and its Practical Impact on Approximation Quality, Arthur Choi and Adnan Darwiche SatisLability II Chair: Ashish Sabharwal New Inference Rules for Ef[cient Max-SAT Solving, Federico Heras and Javier Larrosa Ef[cient Haplotype Inference with Boolean Satis[abili- ty, Inês Lynce and João Marques-Silva Fast SAT-based Answer Set Solver, Zhijun Lin, Yuanlin Zhang, and Hector Hernandez 3:00 3 4:00 PM AI & the Turing Test Chair: Stuart Shapiro Senior: Turing 9s Dream and the Knowledge Challenge, Lenhart Schubert Senior: Does the Turing Test Demonstrate Intelligence or Not? Stuart M. Shieber UAI: Bayesian Networks Chair: Miroslav Velev Identi[ability in Causal Bayesian Networks: A Sound and Complete Algorithm, Yimin Huang and Marco Val- torta Identi[cation of Joint Interventional Distributions in Recursive Semi-Markovian Causal Models, Ilya Shpitser and Judea Pearl A Bayesian Network for Outbreak Detection and Predic- tion, Xia Jiang and Garrick L. Wallstrom SatisLability III Chair: Jussi Rintanen Abstract Branching for Quanti[ed Formulas, Marco Benedetti Solving QBF by Combining Conjunctive and Disjunc- tive Normal Forms, Lintao Zhang DNNF-based Belief State Estimation, Paul Elliott and Brian Williams C ONFERENCE S CHEDULE 4T HURSDAY , J ULY 2013 Seaport A Cityview I (WTC) Harborview II (IAAI) A Coffee break will be held at 10:00-10:20 AM . The lunch break will be held from 12:30 3 1:50 PM . Robotics I Chair: Bernadine Dias Senior: Integrated AI in Space: The Autonomous Science- craft on Earth Observing One, Steve Chien Exploiting Spatial and Temporal Flexibility for Plan Execu- tion for Hybrid, Under-actuated Robots, Andreas G. Hof- mann and Brian C. Williams A Manifold Regularization Approach to Calibration Reduc- tion for Sensor-Network Based Tracking, Jeffrey Junfeng Pan, Qiang Yang, Hong Chang, and Dit-Yan Yeung General Game Playing / Hall of Champions Chair: Mark T. Maybury Automatic Heuristic Construction in a Complete General Game Player, Gregory Kuhlmann and Peter Stone Winning the DARPA Grand Challenge with an AI Robot, Michael Montemerlo, Sebastian Thrun, Hendrik Dahlkamp, David Stavens, and Sven Strohband Running the Table: An AI for Computer Billiards, Michael Smith IAAI-06: Knowledge-Based Agents Chair: Neil Jacobstein Emerging Application: Multiagent Coalition Formation for Computer-Supported Cooperative Learning, Leen-Kiat Soh, Nobel Khandaker, and Hong Jiang Emerging Application: Design and Implementation of the CALO Query Manager, Jose-Luis Ambite, Vinay K. Chaudhri, Richard Fikes, Jessica Jenkins, Sunil Mishra, Maria Muslea, Tomas Uribe, and Guizhen Yang Robotics II Chair: Bernadine Dias Bayesian Calibration for Monte Carlo Localization, Armita Kaboli, Michael Bowling, and Petr Musilek Nectar: Subjective Mapping, Michael Bowling, Dana Wilkin- son, and Ali Ghodsi Ef[cient Triangulation-Based Path[nding, Douglas Demyen and Michael Buro Human-Computer Interaction & Cognitive Modeling: Intelligent Tutoring Systems Chair: Mark T. Maybury Classifying Learner Engagement through Integration of Multiple Data Sources, Carole R. Beal, Lei Qu, and Hyokyeong Lee A Dynamic Mixture Model to Detect Student Motivation and Pro[ciency, Jeff Johns and Beverly Woolf Probabilistic Goal Recognition in Interactive Narrative En- vironments, Bradford Mott, Sunyoung Lee, and James Lester IAAI-06: Constraint-Based Reasoning Deployed Application :Expressive Commerce and Its Appli- cation to Sourcing, Tuomas Sandholm Robotics III Chair: Sven Koenig Senior: From the Programmer 9s Apprentice to Human- Robot Interaction: Thirty Years of Research on Human- Computer Collaboration, Charles Rich and Candace L. Sid- ner Reinforcement Learning with Human Teachers: Evidence of Feedback and Guidance with Implications for Learning Performance, Andrea L. Thomaz and Cynthia Breazeal Diagnosis of Multi-Robot Coordination Failures Using Dis- tributed CSP Algorithms, Meir Kalech, Gal A. Kaminka, Amnon Meisels, and Yehuda Elmaliach Human-Computer Interaction & Cognitive Modeling: Cognitive Modeling Chair: Mark T. Maybury Modeling Human Decision Making in Cliff-Edge Environ- ments, Ron Katz and Sarit Kraus From Pigeons to Humans: Grounding Relational Learning in Concrete Examples, Marc T. Tomlinson and Bradley C. Love Nectar: AI Support for Building Cognitive Models, Robert St. Amant, Sean P. McBride, and Frank E. Ritter IAAI-06: Personalization Technologies Chair: Bruce Porter Emerging Application: CPM: Context-Aware Power Manage- ment in WLANs, Fahd Albinali and Chris Gniady Emerging Application: Trip Router with Individualized Pref- erences (TRIP): Incorporating Personalization into Route Planning, Julia Letchner, John Krumm, and Eric Horvitz Computer Vision Object Boundary Detection in Images using a Semantic Ontology, Anthony Hoogs and Roderic Collins Motion-Based Autonomous Grounding: Inferring External World Properties from Encoded Internal Sensory States Alone, Yoonsuck Choe and Noah H. Smith Nectar: The Role of Context in Head Gesture Recognition, Louis-Philippe Morency, Candace Sidner, Christopher Lee, and Trevor Darrell Competitions at AAAI-06 Chair: Yaxin Liu General Game Playing Competition, Michael Genesereth Mobile Robot Competition, Paul Rybski and Jeffrey Forbes Poker Competition, Martin Zinkevich, University of Alberta IAAI-06: Knowledge-Based Systems 3 Chair: Karen Haigh Deployed Application :TPBOSCourier: A Transportation Procurement System (for the Procurement of Courier Ser- vices), Andrew Lim, Zhou Xu, Brenda Cheang, Ho Wee Kit, and Steve Au-yeung Emerging Application: Hand Grip Pattern Recognition for Mobile User Interfaces, Kee-Eung Kim, Wook Chang, Sung- Jung Cho, Junghyun Shim, Hyunjeong Lee, Joonah Park, Youngbeom Lee, and Sangryoung Kim A limited number of Proceedings (in both book and CD form) are available for purchase in Registration. 14P OSTER S ESSION AAAI-06 Technical Papers Constraint Satisfaction and SatisLability Extending Dynamic Backtracking to Solve Weight- ed Conditional CSPs, Robert T. EfYnger and Bri- an C. Williams Detecting Disjoint Inconsistent Subformulas for Computing Lower Bounds for Max-SAT, Chu- Min Li, Felip Manyà, and Jordi Planes An Asymptot

less