A Bayesian network is a widely used probabilistic graphical model with applications in knowledge discovery and prediction. Learning a Bayesian network (BN) from data can be cast as an optimization problem using the well-known score-andsearch approach. However, selecting a single model (i.e., the best scoring BN) can be misleading or may not achieve the best possible accuracy. An alternative to committing to a single model is to perform some form of Bayesian or frequentist model averaging, where the space of possible BNs is sampled or enumerated in some fashion. Unfortunately, existing approaches for model averaging either severely restrict the structure of the Bayesian network or have only been shown to scale to networks with fewer than 30 random variables. In this paper, we propose a novel approach to model averaging inspired by performance guarantees in approximation algorithms. Our approach has two primary advantages. First, our approach only considers credible models in that they are optimal or near-optimal in score. Second, our approach is more efficient and scales to significantly larger Bayesian networks than existing approaches.

The need for safety in Automated Driving (AD) is becoming increasingly critical with the accelerating deployment of this technology. Beyond functional safety, industry must guarantee the operational safety of automated vehicles. Towards that end, Mobileye introduced the Responsibility Sensitive Safety (RSS), a model-based approach to Safety [1]. In this paper we expand upon this work introducing the C++ Library for Responsibility Sensitive Safety, an open source executable that implements a subset of RSS. We provide architectural details to integrate the C++ Library for Responsibility Sensitive Safety with AD Software pipelines as safety module overseeing decision making of driving policies. We illustrate this application with an example integration with the Baidu Apollo AD stack and simulator, [2] and [3], that provides safety validation of the planning module. Furthermore, we show how the C++ Library for Responsibility Sensitive Safety can be used to explore the usefulness of the RSS model through parameter exploration and analysis on minimum safe longitudinal distance, (dmin), considering different weather conditions. We also compare these results with half-of-speed rule followed in some parts of the world. We expect that the C++ Library for Responsibility Sensitive Safety becomes a critical component of future tools for formal verification, testing and validation of AD safety and that it helps bootstrap the AD research efforts towards standardization of safety.

Focus stacking, or all-in-focus imaging, is a technique for achieving larger depth of field in an image by fusing images acquired at different focusing distances. Minimizing the set of images to fuse, while ensuring that the resulting fused image is all-in-focus, is important in order to avoid long image acquisition and post-processing times. Recently, an end-to-end system for focus stacking has been proposed that automatically selects images to acquire. The system is adaptive to the scene being imaged and shows excellent performance on a mobile device, where the lens has a short focal length and fixed aperture, and few images need to be selected. However, with longer focal lengths, variable apertures, and more selected images (as exists with other cameras, notably DSLRs), classification and algorithmic inaccuracies become apparent. In this paper, we propose improvements to previous work that remove these limitations, and show on eight real scenes that overall our techniques lead to improved accuracy while reducing the number of required images.

In this paper, we show how to boost the performance and speed of the Simple Functions (SF) algorithm for single-image superresolution [1]. This method partitions the low-resolution patch space and learns linear regressors to map low-resolution to highresolution patches. We optimize the partitioning of the patch feature space by first employing dimensionality reduction and then explicitly minimizing the overall super-resolution reconstruction error during training. We also improve selection of training patches. In the super-resolution stage, we use a k-d tree for fast nearest neighbor search of partitions, and combine multiple regression models from neighboring partitions. Experimental results on benchmark data sets show improvements in both image quality and speed over SF. Also, our method outperforms state-of-the-art super-resolution methods in image quality.

We present a method for video super resolution using exemplar images of semantic components. In previous work, we proposed a novel super resolution framework based on semantic components and applied it to still images of human faces. In this paper, we extend the approach to video sequences and propose several methods to overcome temporal jitter that results from standard single frame processing. To achieve consistent selection of facial components from a database of exemplars, we introduce a weighted histogram constructed over a temporal window. We then use pixel-based alignment between the exemplar and input image to reduce temporal jitter of the selected component. To further improve temporal stability, we include a temporal constraint into a final optimization stage that blends high resolution exemplar image data into the upscaled input image. We compare our results on face video clips to those of several state-of-the-art super resolution methods, demonstrating the efficacy of the proposed approach.

Instruction scheduling and instruction selection are two optimization problems that arise in compilers. These problems are considered intractable, and heuristic approaches are currently used in production compilers. In contrast, we have pursued constraint programming approaches that are fast and optimal. The primary goals of this application-driven research were twofold: (i) find solutions of significantly higher quality, and (ii) develop novel constraint programming techniques which have general applicability to similar optimization problems. In this talk, I will describe how successful we were in achieving these goals and some of the lessons we learned along the way.

We present a novel approach to detail enhancement using a dictionary-based technique. For each low-resolution input image patch, we seek a sparse representation from an over-complete dictionary and use that to estimate the high-resolution patch. We modify an existing dictionary-based super-resolution method in several ways to achieve enhancement of fine detail without introduction of new artifacts. These modifications include adaptive enhancement of reconstructed detail patches based on edge analysis to avoid halo artifacts and using an adaptive regularization term to enable noise suppression while enhancing detail. We compare with state-of-the-art methods and show better results in terms of enhancement with suppression of noise.

Some of the core attributes of sports are supposed to be integrity, honesty and sportsmanship. However, there have been numerous cases where individual athletes and teams have thrown games and colluded to manipulate sports competitions. Much of the previous work has focused on proving that some types of competitions are computationally hard to manipulate and thus possibly resistant to manipulation. In contrast, in this paper we focus on detecting patterns of manipulations in sports competitions by coalitions of teams. We show that it is possible to successfully detect certain patterns of manipulations in cups and round robins, two of the most common types of sports competitions. The practical benefit of our approach is a tool that can be used by competition organizers to highlight suspicious play within the competition and so aid in the detection of cheating coalitions.

Previous studies have demonstrated that encoding a Bayesian network into a SAT formula and then performing weighted model counting using a backtracking search algorithm can be an effective method for exact inference. In this paper, we present techniques for improving this approach for Bayesian networks with noisy-OR and noisy-MAX relations---two relations that are widely used in practice as they can dramatically reduce the number of probabilities one needs to specify. In particular, we present two SAT encodings for noisy-OR and two encodings for noisy-MAX that exploit the structure or semantics of the relations to improve both time and space efficiency, and we prove the correctness of the encodings. We experimentally evaluated our techniques on large-scale real and randomly generated Bayesian networks. On these benchmarks, our techniques gave speedups of up to two orders of magnitude over the best previous approaches for networks with noisy-OR/MAX relations and scaled up to larger networks. As well, our techniques extend the weighted model counting approach for exact inference to networks that were previously intractable for the approach.

Caches were designed to amortize the cost of memory accesses by moving copies of frequently accessed data closer to the processor. Over the years the increasing gap between processor speed and memory access latency has made the cache a bottleneck for program performance. Enhancing cache performance has been instrumental in speeding up programs. For this reason several hardware and software techniques have been proposed by researchers to optimize the cache for minimizing the number of misses. Among these are compile-time data placement techniques in memory which improve cache performance. For the purpose of this work, we concern ourselves with the problem of laying out data in memory given the sequence of accesses on a finite set of data objects such that cache-misses are minimized. The problem has been shown to be hard to solve optimally even if the sequence of data accesses is known at compile time. In this paper we show that given a direct-mapped cache, its size, and the data access sequence, it is possible to identify the instances where there are no conflict misses. We describe an algorithm that can assign the data to cache for minimal number of misses if there exists a way in which conflict misses can be avoided altogether. We also describe the implementation of a heuristic for assigning data to cache for instances where the size of the cache forces conflict misses. Experiments show that our technique results in a 30% reduction in the number of cache misses compared to the original assignment.

Modern processors have multiple pipelined functional units and can issue more than one instruction per clock cycle. This places a burden on the compiler to schedule the instructions to take maximum advantage of the underlying hardware. Superblocks - a straight-line sequence of code with a single entry point and multiple possible exit points - are a commonly used scheduling region within compilers. Superblock scheduling is NP-complete, and is done suboptimally in production compilers using a greedy algorithm coupled with a heuristic. The heuristic is usually handcrafted, a potentially time-consuming process. In this paper, we show that supervised machine learning techniques can be used to semiautomate the construction of heuristics for superblock scheduling. In our approach, labeled training data were produced using an optimal superblock scheduler. A decision tree learning algorithm was then used to induce a heuristic from the training data. The automatically constructed decision tree heuristic was compared against the best previously proposed, handcrafted heuristics for superblock scheduling on the SPEC 2000 and MediaBench benchmark suites. On these benchmark suites, the decision tree heuristic reduced the number of superblocks that were not optimally scheduled by up to 38 percent, and led to improved performance on some architectural models and competitive performance on others.

In this paper, we extend a (2-D) data-adaptive steering kernel regression framework for image processing to a (3-D) spatio-temporal framework for processing video. In particular, we propose a motion- assisted steering kernel (MASK) suitable for interpolating video data spatially, temporally, or spatio-temporally, and for video noise reduction. We present an algorithm for multi-frame interpolation and reconstruction of video data, and present several simulation results on synthetic and real video data. Comparisons between single-frame and multi-frame kernel regression and with other methods demonstrate the effectiveness of our approach.

In this study, we propose bit-rate adaptation techniques for compressed high-definition video transmission over wireless home networks. Application-layer methods are developed to minimize quality impairments caused by wireless channel degradations. A transrater located at a home video server adjusts the transmission rate of the video stream based on bandwidth measurements. We consider delay constraints of multiple video frames across various time scales, and dynamically select an appropriate time scale for bit-rate adjustments. This novel feature prevents playout buffer underflows and avoids unnecessary rate reductions. Furthermore, distortion due to transrating is minimized by coding type-dependent rate allocation among the frames to be transmitted in the projected time scale. Using a realistic simulation setup, we demonstrated that the proposed technique significantly reduces video glitches. Up to 3.12 dB average PSNR improvement is achieved, compared to a non-delay constrained rate adaptation method, which also utilizes bandwidth measurements. Our approach maintains compliance with existing wireless local area (WLAN) devices and standards, as well as consumer video standards and applications.

Simultaneous support of multiple video streaming sessions over a shared wireless network requires careful resource allocation to achieve high utilization while dynamically adapting to network and video fluctuations. We propose a distributed algorithm for channel time allocation among multiple video streams, and investigate several heuristic packet pruning schemes for rate adaptation of high-definition (HD) video streams. Simulation results are presented for streaming multiple HD video sequences over an 802.11a network. In comparison with TCP-Friendly Rate Control (TFRC) and a basic scheme without rate adaptation, it is shown that the proposed scheme can sustain higher video quality with lower packet delivery delay.

Constraint satisfaction and prepositional satisfiability problems are often solved using backtracking search. Previous studies have shown that portfolios of backtracking algorithms - a selection of one or more algorithms plus a schedule for executing the algorithms - can dramatically improve performance on some instances. In this paper, we consider a setting that often arises in practice where the instances to be solved arise over time, the instances all belong to some class of problem instances, and a limit or deadline is placed on the computational resources that the backtracking algorithm can consume in solving any instance. For such a scenario, we present a simple scheme for learning a good portfolio of backtracking algorithms from a small sample of instances. We demonstrate the effectiveness of our approach through an extensive empirical evaluation on a real-world instruction scheduling testbed.

We present two new schemes for server-side management of playout delays due to receiver buffering, extending existing techniques such as stream acceleration and adaptive media playout. The first scheme combines stream acceleration with video bit rate adaptation. The second scheme achieves adaptive media playout by server-side frame interpolation combined with bit rate adaptation. The proposed schemes reduce playout delay without decreasing playout robustness. We have performed simulations with wireless IEEE 802.11 channels with varying bandwidth, where the end-to-end delay is dynamically grown from 100 to 500 ms using the proposed schemes. Both our schemes achieve a PSNR performance that is close to that of a scheme with constant end-to-end delay of 500 ms, while retaining the small playout delay of a scheme with constant end-to-end delay of 100 ms. Compared to a scheme with constant end-to-end delay of 100 ms, a PSNR gain up to about 3.4 dB is achieved without increasing the playout delay.

In this paper, we propose a transrating based video rate adaptation technique for compressed high-definition video transmission over wireless local area networks. Our application layer technique targets to prevent the quality impairments caused by inconsistent wireless bandwidth. The transrater at the server adjusts the transmission rate for each video frame, based on bandwidth measurements, to sustain the playout buffer fullness. Client periodically sends feedbacks after probing the available bandwidth using the video packet dispersions. The superiority of the proposed technique over the existing ones comes from its ability to select various time scales for rate adjustments. This feature avoids unnecessary rate reductions. Furthermore, transrating distortion is minimized by encoding type dependent rate allocation among the frames that will be transmitted in the projected time scale. Experimental results show that the proposed technique significantly reduces video glitches. Up to 2.43 dB average PSNR improvement is achieved compared to a delay-constraint unaware rate adaptation method, which also utilizes bandwidth measurements.

Instruction scheduling is one of the most important steps for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block - a straight-line sequence of code with a single entry point and a single exit point - subject to precedence, latency, and resource constraints. Solving the problem exactly is NP-complete, and heuristic approaches are currently used in most compilers. In contrast, we present a scheduler that finds provably optimal schedules for basic blocks using techniques from constraint programming. In developing our optimal scheduler, the key to scaling up to large, real problems was in the development of preprocessing techniques for improving the constraint model. We experimentally evaluated our optimal scheduler on the SPEC 2000 integer and floating point benchmarks. On this benchmark suite, the optimal scheduler was very robust -all but a handful of the hundreds of thousands of basic blocks in our benchmark suite were solved optimally within a reasonable time limit - and scaled to the largest basic blocks, including basic blocks with up to 2600 instructions. This compares favorably to the best previous exact approaches

In this paper, we consider rate adaptation for robust transmission of high-quality video over home networks, in particular IEEE 802.11 wireless LANs. Our approach includes on-line estimation of the time-varying bandwidth available at the application-/transport-layer. We propose a delay-constrained rate adaptation algorithm to select an optimal bit rate, subsequently enforced by a video transcoder. We examine the effectiveness of our novel delay-constrained rate adaptation algorithm, utilizing a simulation environment based on NS-2. Our simulation results show that transmission of MPEG-2 video over an IEEE 802.11b channel results in significantly better quality with rate adaptation compared to transmission without rate adaptation, and that delay-constrained rate adaptation performs significantly better than rate adaptation without a delay constraint.

We consider the transmission of multiple video streams from one server to multiple clients over a shared channel. Transcoders are used to dynamically adapt encoded source rates as link capacities vary. We present a closed-form solution for determining optimal values for the transcoded source rates in this case where multiple video streams with independently varying link capacities share time on a channel. We also present a real-time algorithm for optimized packet transmission scheduling and source pruning. Experimental results show gains of 2.5 dB in PSNR when our optimized pruning and scheduling technique is added to a system that uses transcoding, in the case when there is time lag in the control of transcoders. We also show results in which our pruning scheme performs within 1 dB of off-line, R-D optimal pruning.

Streaming high quality audio/video (AV) from home media sources to TV sets over a wireless local area network (WLAN) is a challenging problem because of the fluctuating bandwidth caused by interference. Our approach is to adjust the video bit-rate dynamically in order to improve the experienced audiovisual quality. The effectiveness of rate adaptation depends on the accurate and timely estimation of the available bandwidth. In this paper we specifically focus on robust video streaming with IEEE 802.11e medium access control (MAC) enhancements for quality-of-service (QoS). These enhancements to 802.11e increase the WLAN throughput and decrease packet latencies. However, bandwidth estimation methods used in prior work, based on packet dispersion measurements, cannot be used in this context. To address this problem, we propose a new on-line application-layer bandwidth measurement method that runs at the sender application and uses the differences of packet send times and feedback receive times. The bandwidth estimation technique is implemented in a video streaming simulation environment that also includes a delay-constrained rate adaptation algorithm at the sender. Experimental results show that streaming with bandwidth estimation and rate adaptation achieves a PSNR gain up to 3.3 dB compared to streaming without rate adaptation

The general solution of satisfiability problems is NP-complete. Although state-of-the-art SAT solvers can efficiently obtain the solutions of many real-world instances, there are still a large number of real-world SAT families which cannot be solved in reasonable time. Much effort has been spent to take advantage of the internal structure of SAT instances. Existing decomposition techniques are based on preprocessing the static structure of the original problem. We present a dynamic decomposition method based on hypergraph separators. Integrating the separator decomposition into the variable ordering of a modern SAT solver leads to speedups on large real-world satisfiability problems. Compared with a static decomposition based variable ordering, such as Dtree (Huang and Darwiche, 2003), our approach does not need time to construct the full tree decomposition, which sometimes needs more time than the solving process itself. Our primary focus is to achieve speedups on large real-world satisfiability problems. Our results show that the new solver often outperforms both regular zChaff and zChaff integrated with Dtree decomposition. The dynamic separator decomposition shows promise in that it significantly decreases the number of decisions for some real-world problems.

We address the problem of robust streaming of high-quality video over wireless local area networks in a home environment. By robust streaming, we mean maintaining the highest possible video quality and preventing interruptions to the video under varying bandwidth conditions, which may be due to distance, interference, obstructions, and existence of multiple streams. We propose an application-layer approach where we provide algorithms for dynamic on-line network bandwidth estimation and dynamic on-line adaptation of video rate according to the available network bandwidth. The proposed system employs a packet scheduler, and a video rate control and adaptation mechanism at the sender, and bandwidth measurement and feedback mechanisms at the receiver. Our bandwidth estimation approach uses the actual video data in real time by transmitting it in packet bursts; hence, separate test traffic is not required. Since the proposed method operates at the application layer, it is flexible and applicable to different local area network types and implementations. We propose an extension to multiple streams by providing an algorithm for joint rate allocation to multiple video streams over a network enabling network-adaptive simultaneous streaming of high-quality video.

Among the chief applications of the MPEG-7 visual descriptors is image indexing and retrieval. And among the colour image descriptors in the standard having the best retrieval performance is the colour structure (CS) descriptor, a descriptor that uses no more storage than an ordinary colour histogram but that substantially out-performs it. The basis of the CS descriptor is the CS histogram, a generalisation of the colour histogram. The CS histogram encodes information about the spatial structure of the colours in an image as well as their frequency of occurrence. Performance is further enhanced by extracting the CS histogram in the novel nonlinear HMMD colour space and by non-uniformly quantising histogram amplitudes to reflect the bin amplitude statistics derived from consumer oriented image databases. The CS descriptor is scalable in the sense that smaller, more compact, CS descriptors can be easily derived from the largest, highest performance descriptor without re-extraction from the image.

In recent years, many improvements to backtracking algorithms for solving constraint satisfaction problems have been proposed. The techniques for improving backtracking algorithms can be conveniently classified as look-ahead schemes and look-back schemes. Unfortunately, look-ahead and look-back schemes are not entirely orthogonal as it has been observed empirically that the enhancement of look-ahead techniques is sometimes counterproductive to the effects of look-back techniques. In this paper, we focus on the relationship between the two most important look-ahead techniques---using a variable ordering heuristic and maintaining a level of local consistency during the backtracking search---and the look-back technique of conflict-directed backjumping (CBJ). We show that there exists a ``perfect'' dynamic variable ordering such that CBJ becomes redundant. We also show theoretically that as the level of local consistency that is maintained in the backtracking search is increased, the less that backjumping will be an improvement. Our theoretical results partially explain why a backtracking algorithm doing more in the look-ahead phase cannot benefit more from the backjumping look-back scheme. Finally, we show empirically that adding CBJ to a backtracking algorithm that maintains generalized arc consistency (GAC), an algorithm that we refer to as GAC-CBJ, can still provide orders of magnitude speedups. Our empirical results contrast with Bessiere and Regin's conclusion (1996) that CBJ is useless to an algorithm that maintains arc consistency.

In order to address the scalability problems of video-on-demand systems, several periodic broadcast schemes have been proposed that partition a video into segments and repetitively broadcast each segment on a separate channel. A new scheme is presented for the bandwidth-efficient periodic broadcast of video. The proposed scheme determines the segment sizes and their corresponding channel bandwidths as a result of a non-linear optimization problem which minimizes the total required bandwidth for the broadcast. The new scheme outperforms the existing schemes in terms of bandwidth demands while it also decouples the playout latency from the number of available channels. Further analysis reveals that its asymptotic bandwidth requirements exactly match the asymptotic bandwidth requirements reported for poly-harmonic broadcasting.

Constraint networks are a simple representation and reasoning framework with diverse applications. In this paper, we identify two new complementary properties on the restrictiveness of the constraints in a network— constraint tightness and constraint looseness —and we show their usefulness for estimating the level of local consistency needed to ensure global consistency, and for estimating the level of local consistency present in a network. In particular, we present a sufficient condition, based on constraint tightness and the level of local consistency, that guarantees that a solution can be found in a backtrack-free manner. The condition can be useful in applications where a knowledge base will be queried over and over and the preprocessing costs can be amortized over many queries. We also present a sufficient condition for local consistency, based on constraint looseness, that is straightforward and inexpensive to determine. The condition can be used to estimate the level of local consistency of a network. This in turn can be used in deciding whether it would be useful to preprocess the network before a backtracking search, and in deciding which local consistency conditions, if any, still need to be enforced if we want to ensure that a solution can be found in a backtrack-free manner. Two definitions of local consistency are employed in characterizing the conditions: the traditional variable-based notion and a recently introduced definition of local consistency called relational consistency .

Many applications -- from planning and scheduling to problems in molecular biology -- rely heavily on a temporal reasoning component. In this paper, we discuss the design and empirical analysis of algorithms for a temporal reasoning system based on Allen's influential interval-based framework for representing temporal information. At the core of the system are algorithms for determining whether the temporal information is consistent, and, if so, finding one or more scenarios that are consistent with the temporal information. Two important algorithms for these tasks are a path consistency algorithm and a backtracking algorithm. For the path consistency algorithm, we develop techniques that can result in up to a ten-fold speedup over an already highly optimized implementation. For the backtracking algorithm, we develop variable and value ordering heuristics that are shown empirically to dramatically improve the performance of the algorithm. As well, we show that a previously suggested reformulation of the backtracking search problem can reduce the time and space requirements of the backtracking search. Taken together, the techniques we develop allow a temporal reasoning component to solve problems that are of practical size.

Constraint networks have been shown to be useful in formulating such diverse problems as scene labeling, natural language parsing, and temporal reasoning. Given a constraint network, we often wish to (i) find a solution that satisfies the constraints and (ii) find the corresponding minimal network where the constraints are as explicit as possible. Both tasks are known to be NP-complete in the general case. Task (1) is usually solved using a backtracking algorithm, and task (ii) is often solved only approximately by enforcing various levels of local consistency. In this paper, we identify a property of binary constraint called row convexity and show its usefulness in deciding when a form of local consistency called path consistency is sufficient to guarantee that a network is both minimal and globally consistent. Globally consistent networks have the property that a solution can be found without backtracking. We show that one can test for the row convexity property efficiently and we show, by examining applications of constraint networks discussed in the literature, that our results are useful in practice. Thus, we identify a class of binary constraint networks for which we can solve both tasks (i) and (ii) efficiently. Finally, we generalize the results for binary constraint networks to networks with nonbinary constraints.

Recognizing the plan underlying a query aids in the generation of an appropriate response. In this paper, we address the problem of how to generate cooperative responses when the user's plan is ambiguous. We show that it is not always necessary to resolve the ambiguity, and provide a procedure that estimates whether the ambiguity matters to the task of formulating a response. The procedure makes use of the critiquing of possible plans and identifies plans with the same fault. We illustrate the process of critiquing with examples. If the ambiguity does matter, we propose to resolve the ambiguity by entering into a clarification dialogue with the user and provide a procedure that performs this task. Together, these procedures allow a question‐answering system to take advantage of the interactive and collaborative nature of dialogue in order to recognize plans and resolve ambiguity. This work therefore presents a view of generation in advice‐giving contexts which is different from the straightforward model of a passive selection of responses to questions asked by users. We also report on a trial implementation in a course‐advising domain, which provides insights on the practicality of the procedures and directions for future research.

Allen gives an algebra for representing qualitative temporal information about the relationships between pairs of intervals. In this paper, we address a fundamental reasoning task that arises in applications of the algebra: Given (possibly indefinite) knowledge about the relationships between intervals, find all feasible relationships between two intervals. We call this the minimal labels problem. Finding the minimal labels can be viewed as computing the deductive consequences of our knowledge. Determining exact solutions to this problem has been shown to be (almost assuredly) intractable. Allen gives an approximation algorithm based on constraint propagation. We present new approximation algorithms; determine analytically under what conditions the algorithms are exact; and examine, through some computational experiments, the quality of the approximate solutions produced by the algorithms. We also give a simple test for predicting when the approximation algorithms will and will not produce good quality approximations. Finally, we survey three example applications of the interval algebra chosen from the literature to show where the results of this paper could be useful.

Previous work in generating explanations from advice-giving systems has demonstrated that a cooperative system can and should infer the immediate goals and plans of an utterance (or discourse segment) and formulate a response in light of these goals and plans. The claim of this paper is that a cooperative response may also have to address a user's overall goals, plans, and preferences among those goals and plans. An algorithm is introduced that generates user-specific responses by reasoning about the goals, plans and preferences hypothesized about a user.