Cees Witteveen

ICAPS Conference 2015 Conference Paper

Temporal Flexibility Revisited: Maximizing Flexibility by Computing Bipartite Matchings

• Kiriakos-Simon Mountakis
• Tomas Klos
• Cees Witteveen

We discuss two flexibility metrics for Simple Temporal Networks (STNs): the so-called naive flexibility metric based on the difference between earliest and latest starting times of temporal variables, and a recently proposed concurrent flexibility metric. We establish an interesting connection between the computation of these flexibility metrics and properties of the minimal distance matrix DS of an STN S: the concurrent flexibility metric can be computed by finding a minimum weight matching of a weighted bipartite graph completely specified by DS, while the naive flexibility metric corresponds to computing a maximum weight matching in the same graph. From a practical point of view this correspondence offers an advantage: instead of using an O(n5) LP-based approach, reducing the problem to a matching problem we derive an O(n3) algorithm for computing the concurrent flexibility metric.

AIJ Journal 2014 Journal Article

Flexibility and decoupling in Simple Temporal Networks

• Michel Wilson
• Tomas Klos
• Cees Witteveen
• Bob Huisman

We propose a new metric to determine the flexibility of a Simple Temporal Network (STN). After reviewing some existing flexibility metrics, we conclude that these metrics fail to capture the dependencies between events specified in the STN. As a consequence, these metrics will usually overestimate the available flexibility in such a system. We propose to use an intuitively more acceptable flexibility metric. This metric is based upon the notion of an interval schedule for an STN. Such an interval schedule specifies an interval for every event in the STN in such a way that, for every event, we are free to choose a starting time within its interval independently from the choice made for other events. We show that an interval schedule that maximizes our flexibility metric is computable in low-order polynomial time. As byproducts of this flexibility metric, we discuss simple solutions to problems in STNs with uncertainty (STNUs) and temporal decoupling in STNs. With respect to the latter we show that after computing our flexibility metric, we get a decomposition of the STN almost for free. Even more importantly, we show that contrary to popular belief, such a decomposition does not affect the flexibility of the original STN.

AAAI Conference 2014 Conference Paper

Optimal Decoupling in Linear Constraint Systems

• Cees Witteveen
• Michel Wilson
• Tomas Klos

Decomposition is a technique to obtain complete solutions by assembling independently obtained partial solutions. In particular, constraint decomposition plays an important role in distributed databases, distributed scheduling and violation detection: It enables conflictfree local decision making, while avoiding communication overloading. One of the main issues in decomposition is the loss of flexibility due to decomposition. Here, flexibility roughly refers to the freedom in choosing suitable values for the variables in order to satisfy the constraints. In this paper, we concentrate on linear constraint systems and efficient decomposition techniques for them. Using a generalization of a flexibility metric developed for Simple Temporal Networks, we show how an efficient decomposition technique for linear constraint systems can be derived that minimizes the loss of flexibility. As a by-product of this decomposition technique, we propose an intuitively attractive flexibility metric for linear constraint systems where decomposition does not incur any loss of flexibility.

IJCAI Conference 2013 Conference Paper

Flexibility and Decoupling in the Simple Temporal Problem

• Michel Wilson
• Tomas Klos
• Cees Witteveen
• Bob Huisman

In this paper we concentrate on finding a suitable metric to determine the flexibility of a Simple Temporal Problem (STP). After reviewing some flexibility metrics that have been proposed, we conclude that these metrics fail to capture the correlation between events specified in the STP, resulting in an overestimation of the available flexibility in the system. We propose to use an intuitively more acceptable flexibility metric based upon uncorrelated time-intervals for the allowed starting times of events in an STP. This metric is shown to be computable in low-polynomial time. As a byproduct of the flexibility computation, we get a decomposition of the STN almost for free: for every possible k-partitioning of the event space, a decomposition can be computed in O(k)-time. Even more importantly, we show that contrary to popular belief, such a decomposition does not affect the flexibility of the original STP.

ECAI Conference 2012 Conference Paper

Enhancing predictability of schedules by task grouping

• Michel Wilson
• Cees Witteveen
• Bob Huisman

An important problem in scheduling is ensuring predictability of solutions in case of execution delays. We propose a new method, task grouping, and apply it in combination with a precedence constraint posting algorithm to solve the resource-constrained project scheduling problem. Using this method tasks that must be executed sequentially can be grouped, but their definitive order is determined at execution time such that delays can sometimes be mitigated. As a consequence, our method generates a set of execution options for a schedule. Using the well-known PSPLIB instances, we show that our method can reduce the impact of delays on the predictability of schedule execution.

AAAI Conference 2012 Conference Paper

Exploiting Shared Resource Dependencies in Spectrum Based Plan Diagnosis

• Shekhar Gupta
• Nico Roos
• Cees Witteveen
• Bob Price
• Johan DeKleer

In case of a plan failure, plan-repair is a more promising solution than replanning from scratch. The effectiveness of plan-repair depends on knowledge of which plan action failed and why. Therefore, in this paper, we propose an Extended Spectrum Based Diagnosis approach that efficiently pinpoints failed actions. Unlike Model Based Diagnosis (MBD), it does not require the fault models and behavioral descriptions of actions. Our approach first computes the likelihood of an action being faulty and subsequently proposes optimal probe locations to refine the diagnosis. We also exploit knowledge of plan steps that are instances of the same plan operator to optimize the selection of the most informative diagnostic probes. In this paper, we only focus on diagnostic aspect of planrepair process.

AAMAS Conference 2011 Conference Paper

Decomposing Constraint Systems: Equivalences and Computational Properties

• Wiebe van der Hoek
• Cees Witteveen
• Michael Wooldridge

Distributed systems can often be modeled as a collection of distributed (system) variables whose values are constrained by a set of constraints. In distributed multi-agent systems, the set of variables occurring at a site (subsystem) is usually viewed as controllable by a local agent. This agent assigns values to the variables, and the aim is to provide distributed methods enabling a set of agents to come up with a global assignment (solution) that satisfies all the constraints. Alternatively, the system might be understood as a distributed database. Here, the focus is on ensuring consistency of the global system if local constraints (the distributed parts of the database) change. In this setting, the aim is to determine whether the existence of a global solution can be guaranteed. In other settings (e. g. , P2P systems, sensor networks), the values of the variables might be completely out of control of the individual systems, and the constraints only characterize globally normal states or behavior of the system. In order to detect anomalies, one specifies distributed methods that can efficiently indicate violations of such constraints. The aim of this paper is to show that the following three main problems identified in these research areas are in fact identical: (i) the problem of ensuring that independent agents come up with a global solution; (ii) the problem of ensuring that global consistency is maintained if local constraint stores change; and (iii) the problem of ensuring that global violations can be detected by local nodes. This claim is made precise by developing a decomposition framework for distributed constraint systems and then extracting preservation properties that must satisfied in order to solve the above mentioned problems. Although satisfying the preservation properties seems to require different decomposition modes, our results demonstrate that in fact these decomposition properties are equivalent, thereby showing that the three main problems identified above are identical. We then show that the complexity of finding such decompositions is polynomially related to finding solutions for the original constraint system, which explains the popularity of decomposition applied to tractable constraint systems. Finally, we address the problem of finding optimal decompositions and show that even for tractable constraint systems, this problem is hard.

IJCAI Conference 2011 Conference Paper

Learning Driving Behavior by Timed Syntactic Pattern Recognition

• Sicco Verwer
• Mathijs de Weerdt
• Cees Witteveen

We advocate the use of an explicit time representation in syntactic pattern recognition because it can result in more succinct models and easier learning problems. We apply this approach to the real-world problem of learning models for the driving behavior of truck drivers. We discretize the values of onboard sensors into simple events. Instead of the common syntactic pattern recognition approach of sampling the signal values at a fixed rate, we model the time constraints using timed models. We learn these models using the RTI+ algorithm from grammatical inference, and show how to use computational mechanics and a form of semi-supervised classification to construct a real-time automaton classifier for driving behavior. Promising results are shown using this new approach.

I&C Journal 2011 Journal Article

The efficiency of identifying timed automata and the power of clocks

• Sicco Verwer
• Mathijs de Weerdt
• Cees Witteveen

We develop theory on the efficiency of identifying (learning) timed automata. In particular, we show that: (i) deterministic timed automata cannot be identified efficiently in the limit from labeled data and (ii) that one-clock deterministic timed automata can be identified efficiently in the limit from labeled data. We prove these results based on the distinguishability of these classes of timed automata. More specifically, we prove that the languages of deterministic timed automata cannot, and that one-clock deterministic timed automata can be distinguished from each other using strings in length bounded by a polynomial. In addition, we provide an algorithm that identifies one-clock deterministic timed automata efficiently from labeled data. Our results have interesting consequences for the power of clocks that are interesting also out of the scope of the identification problem.

AAMAS Conference 2010 Conference Paper

Optimal Temporal Decoupling in Multiagent Systems

• L
• eacute; on Planken
• Mathijs de Weerdt
• Cees Witteveen

When agents need to interact in order to solve some (possibly common) problem, resolving potential conflicts beforehand is often preferred to coordination during execution. Agents may lose some flexibility, but their course of actionwill be more predictable and often also more efficient, obtaining a socially optimal outcome instead of a local optimum. One way to resolve conflicts beforehand is to give extra constraints to each of the agents such that when they allmeet these constraints, the resulting execution is conflict-free. A set of constraints that meets this requirement iscalled a decoupling of the original problem; if it also maximizes the social welfare (i. e. the sum of the valuations ofall the agents), it is called optimal. Representing interestingmultiagent problems as a constraint problem, we show thatfinding an optimal decoupling is at least as hard as finding a solution for the constraint problem. We therefore focus on a constraint problem that is efficiently solvable, butstill very relevant and interesting in the context of multiple agents executing their actions, i. e. the Simple TemporalProblem (STP). Two more technical results, then, are thatwe resolve the open question whether finding an optimal decoupling of the STP is NP-hard (it is), and if all agents havelinear valuation functions, this decoupling problem can besolved efficiently.

AAMAS Conference 2009 Conference Paper

Context-Aware Multi-Stage Routing+

• Adriaan ter Mors
• Jeroen van Belle
• Cees Witteveen

In context-aware route planning, a set of agents has to plan routes on a common infrastructure and each agent has to plan a conflict-free route from a source to a destination without invalidating plans made by other agents. The existence of such a conflict-free set of plans can be ensured if each agent is allowed to reserve time slots on the infrastructure resources it intends to use. In the multi-stage variant of the context-aware routing problem, each agent has a sequence of destination locations it must visit. A naive approach to solve the multi-stage variant is to make context-aware route plans between every two subsequent locations in the sequence, and then to concatenate these plans together. It can easily be shown, however, that this concatenation approach cannot guarantee that a multi-stage plan (if it exists) can always be found, and even if it is found, then it need not be optimal. Therefore, we present a new polynomial-time algorithm for the multi-stage routing problem that always returns the optimal (shortest-time) route for a single agent, given a set of reservations made by previous agents, thus providing a set of Pareto-optimal route plans. Obviously, the need for such a dedicated multi-stage routing algorithm depends on the frequency with which the concatenation approach fails to find a plan, or finds a rather inefficient one. Our experiments show that, given a set of reservations from 200 agents, the concatenation approach fails to find a solution in more than 50% of the cases, for random visiting sequences of six locations or more. However, if the concatenation approach does find a solution, its plan quality is often close to that of an optimal solution.

ECAI Conference 2008 Conference Paper

Diagnosis of Simple Temporal Networks

• Nico Roos
• Cees Witteveen

In many domains successful execution of plans requires careful monitoring and repair. Diagnosis of plan execution supports this process by identifying causes of plan failure.

AAMAS Conference 2008 Conference Paper

Multi-Agent Plan Diagnosis and Negotiated Repair

• Huib Aldewereld
• Pieter Buzing
• Geert Jonker
• Femke de Jonge
• Frank Dignum
• John-Jules Ch. Meyer
• Nico Roos
• Cees Witteveen

In the complex, dynamic domain of Air Traffic Control (ATC) many unexpected events can happen during the execution of a plan. Sometimes these disruptions make the plan infeasible and require a change of the original plan. Unexpected events may disrupt the execution of a plan leading to conflicts concerning the use of shared resources. By monitoring the possibly disrupted execution of a plan, air traffic controllers identify and repair conflicts before they occur, making the plan ‘healthy’ again. Model-based diagnosis helps to identify the causes of observed disruptions in the execution of a plan. This information enables the creation of better plan repairs. These repairs should efficient, but moreover they should be fair, i. e. , one airline should not be the victim of conflicts caused by another. Due to the complexity of planning tasks, it is beneficial to provide a distributed solution such that the workload is spread instead of centralised. Moreover, since the choice between various possible solutions to a conflict in the plan execution directly influence different parties (with diverting interests), the decision about which solution to choose should not be made by a single (central) decision maker, but agreed upon by the different parties involved. The Multi-Agent Diagnosis and negotiated repair (MAD) demonstrator combines our previous research done on model-based diagnosis, planning and scheduling techniques, and methods for multi-agent negotiation to solve this problem in a distributed manner. The resulting tool is a system to support the control and adaptation of distributed plan execution in the domain of ATC.

JAAMAS Journal 2008 Journal Article

Primary and secondary diagnosis of multi-agent plan execution

• Femke de Jonge
• Nico Roos
• Cees Witteveen

Abstract Diagnosis of plan failures is an important subject in both single- and multi-agent planning. Plan diagnosis can be used to deal with plan failures in three ways: (i) to provide information necessary for the adjustment of the current plan or for the development of a new plan, (ii) to point out which equipment and/or agents should be repaired or adjusted to avoid further violation of the plan execution, and (iii) to identify the agents responsible for plan-execution failures. We introduce two general types of plan diagnosis: primary plan diagnosis identifying the incorrect or failed execution of actions, and secondary plan diagnosis that identifies the underlying causes of the faulty actions. Furthermore, three special cases of secondary plan diagnosis are distinguished, namely agent diagnosis, equipment diagnosis and environment diagnosis.

ECAI Conference 2008 Conference Paper

Robust Reservation-Based Multi-Agent Routing

• Adriaan ter Mors
• Xiaoyu Mao
• Jonne Zutt
• Cees Witteveen
• Nico Roos

ICAPS Conference 2007 Conference Paper

Context-Aware Logistic Routing and Scheduling

• Adriaan ter Mors
• Jonne Zutt
• Cees Witteveen

In context-aware route planning, agents have to plan their route on a common infrastructure in such a way that plans made by other agents are not invalidated, and no conflicts are introduced. Previous research on context-aware routing, mostly in the domain of automated guided vehicle (AGV) routing, has reported on an O(n^4v^2) (n the number of vehicles, v the number of infrastructure resources) algorithm. In this paper we present an improved algorithm with a complexity of only O(nv log(nv) + nv^2). Our free path routing approach is based on a search through the graph of free time windows on the resources, rather than a search through the infrastructure itself. Our algorithm can be used to find a set of conflict-free routes for a number of agents by finding the route for a single agent at a time. As a consequence, the order in which agents plan their route will determine the quality not only of the individual agent plans, but also of the global plan. Our experimental results confirm that for an individual agent, its position in the planning queue can make a significant difference; for the total throughput of the airport, however, the order in which the agents make their plans is not highly significant. Also the experiments compare our free path routing approach to fixed path scheduling approaches. We show that for a reasonable amount of extra computation time (required to investigate alternative routes), a free path routing approach finds more efficient plans, because it manages to avoid bottlenecks in the infrastructure.

AAMAS Conference 2007 Conference Paper

Diagnosis of Plan Step Errors and Plan Structure Violations

• Cees Witteveen
• Nico Roos
• Adriaan ter Mors
• Xiaoyu Mao

Failures in plan execution can be attributed to errors in the execution of plan steps or violations of the plan structure. While in previous work we have concentrated on the first type of failures, in this paper we introduce the idea of diagnosing violations in the plan structure. The structure of a plan prescribes which actions have to be performed and which precedence constraints between them have to be respected. Especially in multi-agent environments violations of plan structure might easily occur as the consequence of synchronization errors. Using a formal framework for plan diagnosis, we show how Model-Based Diagnosis can applied to identify these violations of plan structure specifications and we analyze the computational complexity of the associated diagnostic problems.

JAAMAS Journal 2007 Journal Article

Models and methods for plan diagnosis

• Nico Roos
• Cees Witteveen

Abstract We consider a model-based diagnosis approach to the diagnosis of plans. Here, a plan performed by some agent(s) is considered as a system to be diagnosed. We introduce a simple formal model of plans and plan execution where it is assumed that the execution of a plan can be monitored by making partial observations of plan states. These observed states are used to compare them with states predicted based on (normal) plan execution. Deviations between observed and predicted states can be explained by qualifying some plan steps in the plan as behaving abnormally. A diagnosis is a subset of plan steps qualified as abnormal that can be used to restore the compatibility between the predicted and the observed partial state. Besides minimum and subset minimal diagnoses, we argue that in plan-based diagnosis maximum informative diagnoses should be considered as preferred diagnoses, too. The latter ones are diagnoses that make the strongest predictions with respect to partial states to be observed in the future. We show that in contrast to minimum diagnoses, finding a (subset minimal) maximum informative diagnosis can be achieved in polynomial time. Finally, we show how these diagnoses can be found efficiently if the plan is distributed over a number of agents.

JAAMAS Journal 2006 Journal Article

Coordinating Self-interested Planning Agents

• Pieter Buzing
• Adriaan ter Mors
• Cees Witteveen

Abstract We consider planning problems where a number of non-cooperative agents have to work on a joint problem. Such problems consist in completing a set of interdependent, hierarchically ordered tasks. Each agent is assigned a subset of tasks to perform for which it has to construct a plan. Since the agents are non-cooperative, they insist on planning independently and do not want to revise their individual plans when the joint plan has to be assembled from the individual plans. We present a general formal framework to study some computational aspects of this non-cooperative coordination problem and we establish some complexity results to identify some of the factors that contribute to the complexity of this problem. Finally, we illustrate our approach with an application to coordination in multi-modal logistic planning.

EUMAS Conference 2005 Conference Paper

Diagnosis of Plan Execution and the Executing Agent

• Nico Roos
• Cees Witteveen

AAMAS Conference 2005 Conference Paper

Diagnosis of Single and Multi-Agent Plans

• Cees Witteveen
• Nico Roos
• Roman van der Krogt
• Mathijs de Weerdt

AAMAS Conference 2005 Conference Paper

Multiagent Planning through Plan Repair

• Roman van der Krogt
• Mathijs de Weerdt
• Nico Roos
• Cees Witteveen

AAMAS Conference 2003 Conference Paper

A protocol for Multi-Agent Diagnosis with spatially distributed knowledge

• Nico Roos
• Annette Ten Teije
• Cees Witteveen

ECAI Conference 2002 Conference Paper

On Modal Logic Interpretations of Games

• Paul Harrenstein
• Wiebe van der Hoek
• John-Jules Ch. Meyer
• Cees Witteveen

AIJ Journal 2002 Journal Article

Plan coordination by revision in collective agent based systems

• Hans Tonino
• André Bos
• Mathijs de Weerdt
• Cees Witteveen

In order to model plan coordination behavior of agents we develop a simple framework for representing plans, resources and goals of agents. Plans are represented as directed acyclic graphs of skills and resources that, given adequate initial resources, can realize special resources, called goals. Given the storage costs of resources, application costs of skills, and values of goals, it is possible to reason about the profits of a plan for an agent. We then model two forms of plan coordination behavior between two agents, viz. fusion, aiming at the maximization of the total yield of the agents involved, and collaboration, which aims at the maximization of the individual yield of each agent. We argue how both forms of cooperation can be seen as iterative plan revision processes. We also present efficient polynomial algorithms for agent plan fusion and collaboration that are based on this idea of iterative plan revision. Both the framework and the fusion algorithm will be illustrated by an example from the field of transportation, where agents are transportation companies.

ECAI Conference 2000 Conference Paper

Classical, General Frameworks for Recovery

• Wiebe van der Hoek
• Cees Witteveen

AIJ Journal 1998 Journal Article

Recovery of (non)monotonic theories

• Cees Witteveen
• Wiebe van der Hoek

Recovery of a theory T is needed if it does not have a model under the given semantics Sem, i. e. , if the theory is Sem-inconsistent. In general, to recover an inconsistent theory T, a transformation R is applied to T and T is replaced by a consistent theory R(T). If a classical semantics is used, it is clear that R should be a contraction. For nonmonotonic theories, e. g. , nonmonotonic databases, however, in general it is unclear how to restore the consistency of such a theory: indeed, several options for recovery that use (mixtures of) contractions and expansions have been proposed in the literature. In this paper, we propose a more fundamental approach to study the recovery problem by stating some minimal set of rationality postulates for recovery. In these postulates we assume that, when recovering a theory T with respect to some intended semantics, one can fall back on a weaker, so called backup semantics for T. Based on these rationality postulates our general conclusion is that for cumulative theories, expansions are not suitable, while for noncumulative theories like default logic, auto-epistemic logic and nonmonotonic logic programming, contractions cannot be used as recovery operators.

AIJ Journal 1993 Journal Article

Skeptical reason maintenance and belief revision

• Cees Witteveen
• Gerhard Brewka

The skeptical semantics is a three-valued semantics for reason maintenance based on an extension of the well-known two-valued grounded or stable model semantics. Unlike the latter, however, the skeptical semantics has a computationally attractive feature: the skeptical model can be computed in O(n 2) time. The skeptical semantics can also be used to give a better account of the belief revision problem in reason maintenance. A recent logical reconstruction of dependency-directed backtracking (DDB) offers the possibility to represent different DDB strategies by different extensions of a reason maintenance system. Given a reason maintenance system D, we can distinguish a class of extensions, representing all possible DDB strategies for D. We will prove that within this class there exists a unique extension whose skeptical model can be used as a canonical, information-minimal belief revision model. This skeptical belief revision model has some important advantages: 1. (1) The arbitrariness of solutions found by classical dependency-directed backtracking methods can be avoided. 2. (2) The semantics guarantees a (tractable) incremental updating method, and this method satisfies—contrary to standard belief revision techniques—a weak rationality postulate ensuring the minimality of performed changes. 3. (3) Skeptical belief revision is a complete belief revision strategy and is easy to compute, having a worst-case complexity O(n 3).