Study Group

Topics for past and future study group meetings

Intro

To take a bit of time each week to expand our knowledge etc, each week at our technical EUROPA meeting, we will try to have:

• One person suggest a few topics they are interested in learning and presenting at the subsequent meeting, and the group will vote on one topic.
• One person present the topic that was voted on the week before.

Presentations

Date	Presenter	Topic
7/16/08	Tristan	paper: Constructing Conflict-Free Schedules in Space and Time, David W. Hildum and Stephen F. Smith, ICAPS 07
10/01/08	Michael	paper: The Expression Problem Revisited: Four new solutions using generics, Mads Torgersen

Ideas

• D**, D**-light search
• Quad-trees and variants
• Representations of disjunctive temporal networks, or general disjunctive constraint networks
• Conformant planning

Papers Currently on Mike Iatauro's Desk, about which he would be happy to present

• Constraint Tightness versus Global Consistency, Peter van Beek and Rina Dechter
• Planning Graph as a (Dynamic) CSP: Exploiting EBL, DDB, and other CSP Search Techniques in Graphplan, Subbarao Kambhampati
• The Expression Problem Revisited: Four new solutions using generics, Mads Torgersen
• Arc Consistency and Arc Consistency Again, Christian Bessiere
• On Reformulating Planning As Dynamic Constraint Satisfaction (Extended Abstract), Jeremy Frank, Ari K. Jonsson, Paul Morris
• Speeding Up Constraint Propagation, Christian Schulte and Peter J. Stuckey
• Bridging the Gap Between Planning and Scheduling, David E. Smith, Feremy Frank, Ari K. Jonsson
• Random Constraint Satisfaction: Easy Generation of Hard (Satisfiable) Instances, Ke Xu, Frederic Boussemart, Fred Hemery, Christophe Lecoutre
• A Theoretical Evaluation of Selected Backtracking Algorithms, Grzegorz Kondrak and Peter van Beek
• Derivatives of Regular Expressions, Janusz A. Brzozowski
• A Search-Infer-and-Relax Framework for Integrating Solution Methods, J.N. Hooker
• Unifying Local and Exhaustive Search, J.N. Hooker
• In the quest of the best form of local consistency for Weighted CSP, Javier Larrosa, Thomas Schiex
• FF: The Fast-Forward Planning System, Jorg Hoffmann
• Dependent Classes, Vaidas Gasiunas, Mira Mezini, Klaus Ostermann
• Unrestricted Nogood Recording in CSP Search, George Katsirelos and Fahiem Bacchus
• Nogood recording for Static and Dynamic Constraint Satisfaction Problems, Thomas Schiex, Gerard Varfaillie
• A Framework for Dynamic Constraint Reasoning Using Procedural Constraints, Ari K. Jonsson, Jeremy D. Frank
• Hybrid Algorithms for the Constraint Satisfaction Problem, Patrick Prosser
• Trying Again to Fail-First, J. Christopher Beck, Patrick Prosser, and Richard J. Wallace
• Resource, Concurrency, and Local Reasoning, Peter W. O'Hearn (This isn't about resources in the planning sense, exactly, and is both long and dense)
• The Logic of Reachability, David E. Smith, Ari K. Jonsson
• Arc Consistency for General Constraint Networks: preliminary results, Christian Bessiere, Jean-Charles Regin
• Scoping Planning Agents with Shared Models, Tania Bedrax-Weiss, Jeremy D. Frank, Ari K. Jonsson, Conor C. !McGann
• MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems, Christian Bessiere and Jean-Charles Regin
• Remote Agent: to boldly go where no AI system has gone before, Nicola Muscettola, P. Pandurang Nayak, Barney Pell, Brian C. Williams
• An Optimal Coarse-Grained Arc Consistency Algorithm, Christian Bessiere, Jean-Charles Regin, Roland H.C. Yap, Yuanlin Zhang
• Using Metaknowledge to Reduce Arc Consistency Computation, Christian Bessiere, Eugene C. Freuder, Jean-Charles Regin
• An Arc-Consistency Algorithm Optimal in the Number of Constraint Checks, Christian Bessiere and jean-Charles Regin
• Dynamic Backtracking for Dynamic Constraint Satisfaction Problems, Gerard Verfaillie and Thomas Schiex
• Default Timed Concurrent Constraint Programming, Vijay A. Saraswat, Rhada Jagadeesan, Vineet Gupta
• Sparse Constraint Graphs and Exceptionally Hard Problems, Barbara M. Smith and Stuart A. Grant
• Random Constraint Satisfaction: A More Accurate Picture, Dimitris Achlioptas, Michael S. O. Molloy, Lefteris Mk. Kirousis, Yannis C. Stamatiou, Evangelos Kranakis, Danny Kirzanc
• Making AC-3 and Optimal Algorithm Yuanling Zhang and Roland H.C. Yap
• Dynamic Optimization of Interval Narrowing Algorithms, Oliver Lhomme, Arnaud Gotlieb, Micha4el Rueher
• Ordering Heuristics for Arc Consistency Algorithms, Richard J. Wallace and Eugene C. Freuder
• A Generic Arc-Consistency Algorithm and its Specializations, Pascal Van Hentenryck, Yves Deville, Choh-Man Teng
• Refining the Basic Constraint Propagation Algorithm, Christian Bessiere, Jean-Charles Regin
• The Symmetric Alldiff Constraint, Jean-Charles Regin
• Using Inference to Reduce Arc Consistency Computation, Christian Bessiere, Eugene C. Freuder, Jean-Charles Regin
• Computing the Envelope for Stepwise Constant Resource Allocations, Nicola Muscettola
• Stubbornness: a Possible Enhancement for Backjumping and Nogood Recording, Thomas Schiex, Gerard Verfaillie
• Developing Domain-Indpendent Search Control for EUROPA2, Sara Bernardini, David E. Smith
• Bounding the Optimum of Constraint Satisfaction Problems, Simon de Givry, Gerard Verfaillie, and Thomas Schiex
• AND/OR Tree Search for Constraint Optimization, Radu Marinescu and Rina Dechter
• Advances in AND/OR Tree Search for Constraint Optimization, Radu Merinescu and Rina Dechter
• Using Intelligent Backtracking to Improve Branch-and-bound Methods: An Application to Open-Shop Problems, Christielle Gueret, Narendra Jussien, and Christian Prins
• Finding Hard Instances of the Satisfiability Problem: A Survey, Stephen A. Cook and David G. Mitchell
• A Filtering Algorithm for Constraints of Difference in CSPs, Jean-Charles Regin
• Russian Doll Search for Solving Constraint Optimization Problems, Gerard Verfaillie, Michel Lemaitre, Thomas Schiex
• Generating Robust Schedules Through Temporal Flexibility, Nicola Policella, Stephen F. Smith, Amedeo Cesta, Angelo Oddi
• Design, Implementation, and Evaluation of the Constraint Langauge cc(FD), Pascal Van Hentenryck, Vijay Saraswat, and Yves Deville (note: this paper is incomplete, and the available !PostScript version actually crashes the printer)
• A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling Philippe Baptiste, Claude le Pape
• Dynamic Variable Ordering in CSPs, Fahiem Bacchus and Paul van Run
• Optimizing Constraints for Speed: Benchmarking Temporal Logic, I. Jakob
• Formalizing Resources for Planning, Tania Bedrax-Weiss, Conor McGann, Sailesh Ramakrishnan
• Planning as Branch and Bound: A Constraint Programming Implementation
• Algorithms for Rropagating Resource Constraints in AI planning and Scheduling: Existing Approaches and New Results, Philippe Laborie (note that Laborie's method produces bounds that are looser than Nicola's)
• Integrating Algorithms for Weighted CSP in a Constraint Programming Framework, M. Lemaitre, G. Verfaillie, E. Bourreau, F. Laburthe
• Fast Planning Through Planning Graph Analysis, Avrim L. Blum, Merrick L. Furst
• A Tutorial on Planning Graph Based Reachability Heuristics, Daniel Bryce and Subbarao Kambhampati
• Mission Operations Planning with Preferences: An Emperical Study, John L. Bresina, Lina Khatib, and Conor McGann
• Functional Programming in Space, Andrew J. Harris and Daniel Spoonhower
• Maintaining Knowledge About Temporal Intervals, James F. Allen
• The Structure and Performance of Efficient Interpreters, M. Anton Ertl and Davd Gregg
• A New Efficient Algorithm for Solving the Simple Temporal Problem Lin Xu and Berthe Y. Choueiry
• Optimal and Suboptimal Singleton Arc Consistency Algorithms, Christian Bessiere and Romuald Debruyne
• Beam-Stack Search: Integrating Backtracking with Beam Search, Rong Zhou and Eric A. Hansen
• Plan Repair as an Extension of Planning, Roman van der Krogt and Mathijs de Weerdt
• Planning with Goal Preferences and Constraints, Ronen I. Brafman and Yuri Chernyavsky
• Planning Graph Heuristics for Selecting Objectives in Over-subscription Planning Problems, Romeo Sanchez Nigenda and Subbarao Kambhampati
• Discovering Planning Invariants as Anomalies in State Descriptions, Proshanto Mukherji and Lenhart K. Schubert
• Learning Partial-Order Macros from Solutions, Adi Botea, Martin Muller, and Johnathan Shaeffer