Tutorials

Abstract:

Hybrid Systems is a well established field at the interface between control, computer science and mathematics that deals with systems that exhibit both, continuously valued and discretely valued dynamics. It thus provides a powerful modeling scheme to capture the rich dynamic behavior of modern engineering artefacts that exhibit an interplay between continuously valued dynamics and discrete changes among their operational/fault modes. Despite the common goal to model, simulate and analyze systems with hybrid dynamics and to synthesize controllers for them, there exists a large variety of different modeling approaches. The tutorial presents (a) a comprehensive overview among them, (b) introduces common concepts and model characteristics and (c) presents applications within the fields of system's estimation, diagnosis and control. It is our intention to stimulate work that brings together the rich tool-sets of both communities, hybrid systems and planning.

About the Speaker:

Univ.-Prof. Dr. Michael Hofbaur is currently head of the Institute of Automation and Control Engineering at UMIT in Hall/Tyrol, Austria. He received his PhD from Graz University of Technology in 1999. From 2000 to 2001 he worked at MIT's Space Systems and Artificial Intelligence Laboratories. In 2004 he received the venia docendi for the scientific field of Automation and Complex Systems from Graz University of Technology and became full professor at UMIT in 2009. Prof. Hofbaur's research interests include model-based methods for estimation, diagnosis and control of complex hybrid systems, with applications in autonomous mobile and immobile robots.

Abstract:

Model-based diagnosis is a sub-field of artificial intelligence that focuses on formal theories and algorithmic techniques for system-wide fault detection, isolation, and diagnosis. Distinctive features include the use of compositional models to capture nominal and faulty behavior of components and their interaction, and a generic set of reasoning algorithms that use these models and the available observations to identify the most likely hidden health state of the system.

Over the last couple years, these capabilities have been further expanded to model-based systems that perform on-line diagnosis, fault-adaptive control, repair and reconfiguration, and reason on a hybrid of constraint-based and probabilistic models, including hidden Markov models, hierarchical, timed and hybrid automata in order to capture a range of behaviors, including intermittent failures, software components, and continuous dynamics.

This tutorial will give an overview of the field of model-based diagnosis, and focus on its recent growth from model-based diagnosis towards model-based execution, which suggests a rich overlap with the planning community.

Abstract:

RDDL is the Relational Dynamic Influence Diagram Language, the domain modeling language used in the ICAPS 2011 International Probabilistic Planning Competition. RDDL has been developed to compactly model real-world planning problems that use boolean, multi-valued, integer and continuous variables, unrestricted concurrency, non-fluents, probabilistic independence among complex effects (important for exogenous events), aggregation operators in addition to quantifiers, and partial observability. While RDDL addresses some of the probabilistic modeling limitations of PPDDL, it's deterministic subset also addresses some modeling limitations of PDDL (e.g., models needing nonlinear difference equations or unrestricted concurrency). This tutorial provides a general introduction to RDDL, it's semantics, and a number of detailed discrete and continuous planning domain examples to demonstrate it's expressive power. It also provides a brief introduction to the rddlsim software that permits the simulation, evaluation, and visualization of planners and planning domains.

Abstract:

Decision diagrams have proved to be a useful data structure for model checking, temporal verification, graphical model inference, and factored planning (factored MDPs and POMDPs among many applications). This tutorial will cover the foundations of binary and algebraic decision diagrams (BDDs & ADDs) -- their properties, their algorithms, their use in various automated planning settings (including a discussion of when other techniques are preferable to decision diagrams), and tricks of the trade (variable orderings, approximation, and application-specific operations) that help one achieve maximal efficiency in practice. Beyond BDDs and ADDs, the tutorial will also cover a variety of less-used but important decision diagrams and their applications: Zero-suppressed DDs (ZDDs) for set representation and Affine ADDs (AADDs) for arithmetic function representation. The tutorial will end with recent extensions of decision diagrams to support continuous variables that allow the efficient and exact solution of a range of hybrid discrete and continuous planning problems.

Abstract:

Many planning problems can be seen as shortest-path problems in a state-space graph. Heuristic search techniques try to speed up generic shortest-path algorithms by using domain-specific information. This tutorial provides an introduction to classic heuristic search algorithms such as A*, IDA*, greedy best-first search, and weighted A*. Both theoretical and implementation issues will be discussed, pretty pictures will be shown, and no question will be too simple to be entertained.

Abstract:

We'll start with algorithms for finding optimal solutions in contexts where basic algorithms fail (eg, memory for A* and duplicates or real values for IDA*). Then we'll move on to various suboptimal settings: searching for any solution, searching for solutions under cost bounds, and searching under time bounds. We'll discuss how to incorporate inadmissible heuristics and estimates of solution length to speed up search. Our emphasis will be on distinguishing different problem settings, identifying algorithms that apply to each, and developing intuitions for when each algorithm will perform well or poorly.