Capacity-aware Sequential Recommendations

Personalized recommendations are increasingly important to engage users and guide them through large systems, for example when recommending points of interest to tourists visiting a popular city. To maximize long-term user experience, the system should consider issuing recommendations sequentially, since by observing the user's response to a...

Preallocation and Planning under Stochastic Resource Constraints

Resource constraints frequently complicate multi-agent planning problems. Existing algorithms for resource-constrained, multi-agent planning problems rely on the assumption that the constraints are deterministic. However, frequently resource constraints are themselves subject to uncertainty from external influences. Uncertainty about constraints...

Bootstrapping LPs in Value Iteration for Multi-Objective and Partially Observable MDPs

Iteratively solving a set of linear programs (LPs) is a common strategy for solving various decision-making problems in Artificial Intelligence, such as planning in multi-objective or partially observable Markov Decision Processes (MDPs). A prevalent feature is that the solutions to these LPs become increasingly similar as the solving algorithm...

Bounding the probability of resource constraint violations in multi-agent MDPs

Multi-agent planning problems with constraints on global resource consumption occur in several domains. Existing algorithms for solving Multi-agent Markov Decision Processes can compute policies that meet a resource constraint in expectation, but these policies provide no guarantees on the probability that a resource constraint violation will...

Accelerated Vector Pruning for Optimal POMDP Solvers

Partially Observable Markov Decision Processes (POMDPs) are powerful models for planning under uncertainty in partially observable domains. However, computing optimal solutions for POMDPs is challenging because of the high computational requirements of POMDP solution algorithms. Several algorithms use a subroutine to prune dominated vectors in...

Planning Under Uncertainty for Aggregated Electric Vehicle Charging with Renewable Energy Supply

Renewable energy sources introduce uncertainty regarding generated power in smart grids. For instance, power that is generated by wind turbines is time-varying and dependent on the weather. Electric vehicles will become increasingly important in the development of smart grids with a high penetration of renewables, because their flexibility makes...

Planning under Uncertainty for Aggregated Electric Vehicle Charging using Markov Decision Processes

The increasing penetration of renewable energy sources and electric vehicles raises important challenges related to the operation of electricity grids. For instance, the amount of power generated by wind turbines is time-varying and dependent on the weather, which makes it hard to match flexible electric vehicle demand and uncertain wind power...

Solving Transition-Independent Multi-agent MDPs with Sparse Interactions

In cooperative multi-agent sequential decision making under uncertainty, agents must coordinate to find an optimal joint policy that maximises joint value. Typical algorithms exploit additive structure in the value function, but in the fully-observable multi-agent MDP (MMDP) setting such structure is not present. We propose a new optimal solver...

Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making

When multiple independent agents use a limited shared resource, they need to coordinate and thereby their planning problems become coupled. We present a resource assignment strategy that decouples agents using marginal utility cost, allowing them to plan individually. We show that agents converge to an expected cost curve by keeping a history of...

Planning under Uncertainty with Weighted State Scenarios

In many planning domains external factors are hard to model using a compact Markovian state. However, long-term dependencies between consecutive states of an environment might exist, which can be exploited during planning. In this paper we propose a scenario representation which enables agents to reason about sequences of future states. We show...

A Scenario State Representation for Scheduling Deferrable Loads under Wind Uncertainty

Integration of renewable energy in power systems is a potential source of uncertainty, because renewable generation is variable and may depend on changing and highly uncertain weather conditions. In this paper we present and evaluate a new method to schedule power-demanding tasks with release times and deadlines under uncertainty, in order to...

Approximate Solutions for Factored Dec-POMDPs with Many Agents (abstract)

Dec-POMDPs are a powerful framework for planning in multiagent systems, but are provably intractable to solve. This paper proposes a factored forward-sweep policy computation method that tackles the stages of the problem one by one, exploiting weakly coupled structure at each of these stages. An empirical evaluation shows that the loss in...

Planning under Uncertainty for Coordinating Infrastructural Maintenance (abstract)

Scheduling of infrastructural maintenance poses a complex multi-agent problem. Commonly a central authority is responsible for the quality and throughput of the infrastructure, while the actual maintenance is performed by multiple self-interested contractors. Not only does the central authority have to (economically) incentivise agents to...

Enhancing SAT Based Planning with Landmark Knowledge

Several approaches exist to solve Artificial Intelligence planning problems, but little attention has been given to the combination of using landmark knowledge and satisfiability (SAT). Landmark knowledge has been exploited successfully in the heuristics of classical planning. Recently it was also shown that landmark knowledge can improve the...

Planning under Uncertainty for Coordinating Infrastructural Maintenance

We address efficient planning of maintenance activities in infrastructural networks, inspired by the real-world problem of servicing a highway network. A road authority is responsible for the quality, throughput and maintenance costs of the network, while the actual maintenance is performed by autonomous, third-party contractors. From a (multi...

Dynamic Mechanism Design for Efficient Planning under Uncertainty

We study the planning of maintenance activities on public infrastructural networks – road networks, Internet, power grids, etc. – in contingent environments such that the negative impact on the network user is minimised. Traditional efforts hereto are mainly of a regulatory nature, whereas we propose charging the service-providers (agents)...

Tree-Based Solution Methods for Multiagent POMDPs with Delayed Communication (extended abstract)

Multiagent Partially Observable Markov Decision Processes (MPOMDPs) provide a powerful framework for optimal decision making under the assumption of instantaneous communication. We focus on a delayed communication setting (MPOMDP-DC), in which broadcasted information is delayed by at most one time step. In this paper, we show that computation of...

Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion (extended abstract)

We advance the state of the art in optimal solving of decentralized partially observable Markov decision processes (Dec-POMDPs), which provide a formal model for multiagent planning under uncertainty.