Abstract: In this talk I will present several principles behind state of the art algorithms for solving combinatorial optimization tasks defined over graphical models (Bayesian networks, Markov networks, constraint networks, satifiability) and demonstrate their performance on some benchmarks. Applications to planning and scheduling will be highlighted.

Specifically I will present branch and bound search algorithms which explore the AND/OR search space over graphical models and thus exploit problem’s decomposition (using AND nodes), equivalence (by caching) and pruning irrelevant subspaces via the power of bounding heuristics. In particular I will show how the two ideas of  mini-bucket partitioning which relaxes the input problem using node duplication only, combined with linear programming relaxations ideas which optimize cost-shifting/re-parameterization schemes, can yield tight bounding heuristic information within systematic, anytime, search.

notably, a solver for finding the most probable explanation (MPE or MAP), embedding these principles has won first place in all time categories in the 2012 PASCAL2 approximate inference challenge, and first or second place in the UAI- 2014 competitions

Parts of this work were done jointly with: Radu Marinescu, Robesrt Mateescu, Lars Otten, Alex Ihler, Natalia Flerova and Kalev Kask

Bio: Rina Dechter is a professor of Computer Science at the University of California, Irvine. She received her PhD in Computer Science at UCLA in 1985, an MS degree in Applied Mathematics from the Weizmann Institute and a B.S in Mathematics and Statistics from the Hebrew University, Jerusalem. Her research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing and probabilistic reasoning.

Professor Dechter is an author of ‘Constraint Processing’ published by Morgan Kaufmann, 2003, and ‘Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms’ by Morgan and Claypool publishers, 2013, has authored over 150 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research and journal of Machine Learning (JLMR). She was awarded the Presidential Young investigator award in 1991, is a fellow of the American association of Artificial Intelligence since 1994, was a Radcliffe Fellowship 2005-2006, received the 2007 Association of Constraint Programming (ACP) research excellence award and is a 2013 Fellow of the ACM. She has been  Co-Editor-in-Chief of Artificial Intelligence, since 2011.

Workshop Aim

The workshop aims to provide a stable forum on relevant topics connected to application-focused research and the deployment of P&S systems. The immediate legacy began in 2007 with the ICAPS'07 Workshop on Moving Planning and Scheduling Systems into the Real World, and continued in 2008-2014 with successful yearly editions.

The websites of the previous editions of the workshop series are available at http://decsai.ugr.es/~lcv/SPARK/. These workshops presented a stimulating environment where researchers could discuss the opportunity and challenges in moving P&S developments into practice, and analyze domains and problem instances under study for, or closely inspired by, real industrial/commercial deployment of P&S techniques.

This is the 9th edition of SPARK. The previous editions saw substantial attendance with respect to other collocated events (about 30+ people every year since 2007). This success, together with the recent creation of the Novel Applications track at ICAPS make SPARK:

• The ideal incubator to test, discuss, mature and improve potential papers for that main track with the feedback of an excellent audience
• A great place for the inception of new applications and challenges

The challenges and discussions that emerged in the last years' editions set the baseline for this year's SPARK workshop. A goal of the workshop series is the definition of a longer term set of challenges that could be of benefit for the research community as well as practitioners.

Authors of accepted papers will be encouraged to share their domains and instances, or parts of them, towards a library of practical benchmarking problems that could also be useful for the community.

Format

The workshop will retain the successful format of previous SPARK editions. In order to foster discussion amongst speakers and attendees, reviewers of submissions will be asked to write a public critique of each paper composed by a set of public questions or thoughts, in addition to regular private comments to the authors and confidential comments to the organizers. These critiques will also be provided to the authors in advance of the workshop and distributed among the workshop attendees.

Each session will consist of presentations of technical papers, their commentaries, and a short discussion on the topic of papers. The SPARK'15 workshop will feature a panel discussion aiming at wrapping up all the relevant issues and challenges as possible propositions for future editions of the series.

Topics

Starting from the results of the previous editions, SPARK'15 will deepen the debate on application-relevant aspects of P&S theory and practice, with the aim of reporting and discussing experiences relating to deploying P&S systems. Topics of the workshop include, but are not limited to:

• Novel domains and benchmark or challenge problems
• Experiences in deploying P&S systems, from their conception to their maturity in practice
• Comparison with previously existing technologies and/or systems
• Integration of operational knowledge from existing legacy components
• Integration of multiple sources of knowledge and reasoning schemes (actions, time, resources)
• Modelling and domain model acquisition
`
• Handling dynamic and uncertain sources of knowledge
• Algorithmic and technological issues
• Plan execution and replanning
• Mixed initiative approaches
• User interface design, visualization and explanation
• Machine learning methodologies applied to P&S systems
• Engineering, deployment, and maintenance
• Evaluation, testing, and validation
• Assessment of impact on end users

Submission Information

Submissions may be regular papers (6-8 pages, plus references) or short position papers (at most 2 pages, including references). All papers should conform to the AAAI formatting guidelines and style. Submissions will be reviewed by at least two referees. Interested contributors are invited to communicate their intent to submit to the workshop organizers.

Submissions, in PDF format, may be submitted via the EasyChair site: https://easychair.org/conferences/?conf=spark15

All workshop participants must be registered for ICAPS'15 or one of the co-located conferences.

Important Dates

• Submission deadline for papers: February 20, 2015 EXTENDED: March 6, 2015.
• Notification of acceptance/rejection: March 20, 2015 March 27, 2015
• Camera-ready version due: TBD
• Workshop date: June 8th, 2015

Organization

• Steve Chien, NASA Jet Propulsion Laboratory, USA
• Mark Giuliano, Space Telescope Science Institute, USA
• Riccardo Rasconi, ISTC-CNR, Italy

Programme Committee

• Mark Boddy, Adventium Labs, USA
• Luis Castillo, University of Granada, Spain
• Steve Chien, NASA Jet Propulsion Laboratory, USA
• Riccardo de Benedictis, ISTC-CNR, Italy
• Minh Do, NASA Ames, USA
• Simone Fratini, ESA-ESOC, Germany
• Mark Giuliano, Space Telescope Science Institute, USA
• Christophe Guettier, SAGEM, France
• Patrik Haslum, NICTA, Australia
• Russell Knight, NASA Jet Propulsion Laboratory, USA
• Angelo Oddi, ISTC-CNR, Italy
• Bryan O'Gorman, NASA Ames, USA
• Nicola Policella, ESA-ESOC, Germany
• Cedric Pralet, ONERA, France
• Riccardo Rasconi, ISTC-CNR, Italy
• Tiago Vaquero, University of Toronto, Canada
• Ramiro Varela, Universityof Oviedo, Spain
• Terry Zimmerman, University of Washington, USA