ICAPS 2010 Invited Speakers

ICAPS/AAMAS 2010 Joint Invited Speaker: Daniele Nardi (Sheraton, Friday May 14, 8:30)

Robotic Agents for Disaster Response Robotics

Disaster Response Robotics is a challenging domain, where the need for intelligent robotic agents (as opposed to just robots) is motivated both by technical considerations and in a practical application perspective. In emergency scenarios time is critical. Hence, there is a great demand for tools that improve the effectiveness of operations. Although there are specific actions that can be accomplished by a robot, such as for example bomb disposal, a key goal of disaster response robots is to acquire knowledge about the scenario. In fact, a robot can gather data in places that would be either dangerous or inaccessible to the human operator. This often means that the robot is typically not under the visual control of the operator, and sometimes also not connected by a communication link. Consequently, teleoperation can be difficult, if not impossible, and the need arises for intelligent and autonomous capabilities. Moreover, the use of multiple robots naturally stands as a possible breakthrough, given also that disaster scenarios are typically spatially distributed. New challenges hence come up in terms of autonomy, cooperation and collective behaviors.

In the first part of the talk, I briefly overview the state of the art in the field of disaster response robotics, in order to support the above sketched analysis. In the second part of the talk, I present some of the research we developed at Sapienza Univ. of Rome, also in collaboration with the Italian Firemen Department. Specifically, I describe some results in Distributed Situation Assessment, Action Planning and Monitoring, Context-based Design of intelligent robotic agents, Multi-robot Teams for disaster response robotics, and Performance Evaluation Metrics for intelligent robotic agents. Throughout the discussion, I focus on several open challenges that need to be addressed to provide effective solutions for Disaster Response Robotics.

ICAPS 2010 Invited Speaker: Moshe Vardi (Sutton, Saturday May 15, 9:00)

From Automated Verification to Automated Design

One of the most significant developments in the area of design verification over the last decade is the development of algorithmic methods for verifying temporal specification of finite-state designs. A frequent criticism against this approach, however, is that verification is done after significant resources have already been invested in the development of the design. Since designs invariably contains errors, verification simply becomes part of the debugging process. The critics argue that the desired goal is to use the specification in the design development process in order to guarantee the development of correct designs. This is called automated design (or synthesis). In this talk I will review 50 years of research on automated design and show how the automata-theoretic approach can be used to solve it.

ICAPS 2010 Invited Speaker: Holger Hoos (Sutton, Sunday May 16, 9:00)

Computer-Aided Algorithm Design: Automated Tuning, Configuration, Selection and Beyond

High-performance algorithms can be found at the heart of many software systems; they often provide the key to effectively solving the computationally difficult problems encountered in the application areas in which these systems are deployed. Examples of such problems include planning, scheduling, timetabling, resource allocation, computer-aided design and software verification. Many of these problems are NP-hard and considered computationally intractable; nevertheless, these `intractable' problems arise in practice, and finding good solutions to them in many cases tends to become more difficult as economic constraints tighten.

In most (if not all) cases, the key to solving such computationally challenging problems lies in the use of high-performance heuristic algorithms, that is, algorithms that make use of mechanisms whose efficacy can be demonstrated empirically, yet remains inaccessible to the analytical techniques used for proving theoretical complexity results.

High-performance heuristic algorithms are typically constructed in an iterative, manual process in which the designer gradually introduces or modifies components or mechanisms whose performance is then tested by empirical evaluation on one or more sets of benchmark problems. During this iterative design process, the algorithm designer has to make many decisions, ranging from choices of the heuristic mechanisms to be used and the details of these mechanisms to lower-level implementation details, such as data structures. Some of these choices take the form of parameters, whose values are guessed or determined based on limited experimentation.

This traditional approach for designing high-performance algorithms can and often does lead to satisfactory results. However, it tends to be tedious and labour-intensive; furthermore, the resulting algorithms are often unnecessarily complicated, yet fail to realise the full performance potential present in the space of designs that can be built using the same underlying set of components and mechanisms.

As an alternative to the traditional, manual algorithm design process, we advocate an approach that uses fully formalised procedures, implemented in software, to permit a human designer to explore large design spaces more effectively, with the aim of realising algorithms with desirable performance characteristics. Computer-aided algorithm design allows human designers to focus on the creative task of specifying a design space in terms of potentially useful components. This design space is then explored using optimisation and machine learning techniques, in combination with significant amounts of computing power, in order to find algorithms that perform well on given sets or distributions of input instances.

Automated parameter tuning, algorithm configuration, algorithm portfolios and per-instance algorithm selection are prominent special cases of computer-aided algorithm design and have recently played a pivotal role in improving the state of the art in solving a broad range of challenging combinatorial problems, ranging from propositional satisfiability (SAT) and mixed integer programming to protein structure prediction, course timetabling and planning problems.

In this talk, I will introduce computer-aided algorithm design and discuss its main ingredients: design patterns, which provide ways of structuring potentially large spaces of candidate algorithms, and meta-algorithmic optimisation procedures, which are used for finding good designs within these spaces. After explaining how this algorithm design approach differs from and complements related approaches in program synthesis, genetic programming and so-called hyper-heuristics, I will illustrate its success using examples from our own work in SAT-based software verification, timetabling and mixed integer programming. Furthermore, I will argue why this approach can be expected to be particularly useful and effective for building better solvers for rich and diverse classes of combinatorial problems, such as planning and scheduling. Finally, I will outline out how programming by optimisation -- a design paradigm that emphasises the automated construction of performance-optimised algorithm by means of searching large spaces of alternative designs -- has the potential to transform the design of high-performance algorithm from a craft that is based primarily on experience and intuition into a principled and highly effective engineering effort.