We introduce the Cooperative Multi-Agent Path Finding (Co-MAPF) problem, an extension to the classical MAPF problem, where cooperative behavior is incorporated. In this setting, a group of autonomous agents operate in a shared environment and have to complete cooperative tasks while avoiding collisions with the other agents in the group. This extension naturally models many real-world applications, where groups of agents are required to collaborate in order to complete a given task. To this end, we formalize the Co-MAPF problem and introduce Cooperative Conflict-Based Search (Co-CBS), a CBS-based algorithm for solving the problem optimally for a wide set of Co-MAPF problems. Co-CBS uses a cooperation-planning module integrated into CBS such that cooperation planning is decoupled from path planning. Finally, we present empirical results on several MAPF benchmarks demonstrating our algorithm’s properties.

In recent years, there has been an increasing interest in building video summarization tools, where the goal is to automatically create a short summary of an input video that properly represents the original content. We consider shot-based video summarization where the summary consists of a subset of the video shots which can be of various lengths. A straightforward approach to maximize the representativeness of a subset of shots is by minimizing the total distance between shots and their nearest selected shots. We formulate the task of video summarization as an optimization problem with a knapsack-like constraint on the total summary duration. Previous studies have proposed greedy algorithms to solve this problem approximately, but no experiments were presented to measure the ability of these methods to obtain solutions with low total distance. Indeed, our experiments on video summarization datasets show that the success of current methods in obtaining results with low total distance still has much room for improvement. In this paper, we develop ILS-SUMM, a novel video summarization algorithm to solve the subset selection problem under the knapsack constraint. Our algorithm is based on the well-known metaheuristic optimization framework - Iterated Local Search (ILS), known for its ability to avoid weak local minima and obtain a good near-global minimum. Extensive experiments show that our method finds solutions with significantly better total distance than previous methods. Moreover, to indicate the high scalability of ILS-SUMM, we introduce a new dataset consisting of videos of various lengths.

Instability and variability of Deep Reinforcement Learning (DRL) algorithms tend to adversely affect their performance. Averaged-DQN is a simple extension to the DQN algorithm, based on averaging previously learned Q-values estimates, which leads to a more stable training procedure and improved performance by reducing approximation error variance in the target values. To understand the effect of the algorithm, we examine the source of value function estimation errors and provide an analytical comparison within a simplified model. We further present experiments on the Arcade Learning Environment benchmark that demonstrate significantly improved stability and performance due to the proposed extension.

We consider the Max K-Armed Bandit problem, where a learning agent is faced with several stochastic arms, each a source of i.i.d. rewards of unknown distribution. At each time step the agent chooses an arm, and observes the reward of the obtained sample. Each sample is considered here as a separate item with the reward designating its value, and the goal is to find an item with the highest possible value. Our basic assumption is a known lower bound on the \em tail function of the reward distributions. Under the PAC framework, we provide a lower bound on the sample complexity of any (ε,δ)-correct algorithm, and propose an algorithm that attains this bound up to logarithmic factors. We provide an analysis of the robustness of the proposed algorithm to the model assumptions, and further compare its performance to the simple non-adaptive variant, in which the arms are chosen randomly at each stage.

The problem of approachability in repeated games with vector payoffs was introduced by Blackwell in the 1950s, along with geometric conditions and corresponding approachability strategies that rely on computing a sequence of direction vectors in the payoff space. For convex target sets, these vectors are obtained as projections from the current average payoff vector to the set. A recent paper by Abernethy, Batlett and Hazan (2011) proposed a class of approachability algorithms that rely on Online Linear Programming for obtaining alternative sequences of direction vectors. This is first implemented for target sets that are convex cones, and then generalized to any convex set by embedding it in a higher-dimensional convex cone. In this paper we present a more direct formulation that relies on general Online Convex Optimization (OCO) algorithms, along with basic properties of the support function of convex sets. This leads to a general class of approachability algorithms, depending on the choice of the OCO algorithm and the used norms. Blackwell's original algorithm and its convergence are recovered when Follow The Leader (or a regularized version thereof) is used for the OCO algorithm.

No-regret algorithms has played a key role in on-line learning and prediction problems. In this paper, we focus on a generalized no-regret problem with vector-valued rewards, defined in terms of a desired reward set of the agent. For each mixed action q of the opponent, the agent has a set R(q) where the average reward should reside. In addition, the agent has a response mixed action p which brings the expected reward under these two actions, r(p, q), to R(q). If a strategy of the agent ensures that the average reward converges to R(\barq_n), where \barq_n is the empirical distribution of the opponent’s actions, for any strategy of the opponent, we say that it is a no-regret strategy with respect to R(q). The standard no-regret problem is obtained as a special case for scalar rewards and R(q) = r ∈R: r ≥r(q), where r(q) = \max_p r(p, q). For this problem, the multifunction R(q) is convex, and no-regret strategies can be devised. Our main interest in this paper is in cases where this convexity property does not hold. The best that can be guaranteed in general then is the convergence of the average reward to R^c(\barq_n), the convex hull of R(\barq_n). However, as the game unfolds, it may turn out that the opponent’s choices of actions are limited in some way. If these restrictions were known in advance, the agent could possibly ensure convergence of the average reward to some desired subset of R^c(\barq_n), or even approach R(\barq_n) itself. We formulate appropriate goals for opportunistic no-regret strategies, in the sense that they may exploit such limitations on the opponent’s action sequence in an on-line manner, without knowing them beforehand. As the main technical tool, we propose a class of approachability algorithms that rely on a calibrated forecast of the opponent’s actions, which are opportunistic in the above mentioned sense. As an application, we consider the online no-regret problem with average cost constraints, introduced in Mannor, Tsitsiklis, and Yu (2009), where the best-response-in-hindsight is not generally attainable, but only its convex relaxation. Our proposed algorithm applied to this problem does attain the best-response-in-hindsight if the opponent’s play happens to be stationary (either in terms of its mixed actions, or the empirical frequencies of its pure actions).

We consider the online binary classification problem, where we are given m classifiers. At each stage, the classifiers map the input to the probability that the input belongs to the positive class. An online classification meta-algorithm is an algorithm that combines the outputs of the classifiers in order to attain a certain goal, without having prior knowledge on the form and statistics of the input, and without prior knowledge on the performance of the given classifiers. In this paper, we use sensitivity and specificity as the performance metrics of the meta-algorithm. In particular, our goal is to design an algorithm which satisfies the following two properties (asymptotically): (i) its average false positive rate (fp-rate) is under some given threshold, and (ii) its average true positive rate (tp-rate) is not worse than the tp-rate of the best convex combination of the m given classifiers that satisfies fp-rate constraint, in hindsight. We show that this problem is in fact a special case of the regret minimization problem with constraints, and therefore the above goal is not attainable. Hence, we pose a relaxed goal and propose a corresponding practical online learning meta-algorithm that attains it. In the case of two classifiers, we show that this algorithm takes a very simple form. To our best knowledge, this is the first algorithm that addresses the problem of the average tp-rate maximization under average fp-rate constraints in the online setting.

We consider a time-slotted multipacket reception channel, shared by a finite number of mobile users who transmit to a common base station. Each user is allocated a fixed data rate, which may be imposed by the base station or self-determined. For sustaining the required rate over time, each user may adjust a single parameter which determines the individual transmission probability in a given slot. An equilibrium point is attained when the assigned data rates are met with equality. This paper analyzes the equilibrium points which result in this system, with a focus on power efficiency of the solution. While multiple equilibrium points exist in general, we establish that one of these equilibria is best for all users, in the sense that the transmission probability (hence the power investment) of each user is minimal. Further to the existence of worse equilibrium points, we point to the possibility of a partial- equilibrium with starvation, where stronger users (in terms of received power) satisfy their data rates, while preventing weaker ones from obtaining their respective rates. To avoid these sub- optimal working points, we suggest a distributed mechanism that converges to the best equilibrium point. Further analysis is provided for a specific channel model which involves perfect capture.

We consider a wireless collision channel, shared by a finite number of users who transmit to a common base station. Users are self-optimizing, and each wishes to minimize its average transmission rate (or power investment), subject to minimum- throughput demand. The channel quality between each user and the base station is time-varying, and partially observed by the user in the form of channel state information (CSI) signals. We assume that each user can transmit at a fixed power level and that its transmission decision at each time slot is stationary in the sense that it can depend only on the current CSI. We are interested in properties of the Nash equilibrium of the resulting game between users. We define the feasible region of user's throughput demands, and show that when the demands are within this region, there exist exactly two Nash equilibrium points, with one strictly better than the other (in terms of invested power) for all users. We further provide some lower bounds on the channel capacity that can be obtained, both in the symmetric and non-symmetric case. Finally, we show that a simple greedy mechanism converges to the best equilibrium point without requiring any coordination between the users.

We consider a wireless collision channel, shared by a finite number of mobile users who transmit to a common base station using a random access protocol. Mobiles are self-optimizing, and wish to minimize their individual average power investment subject to minimum-throughput demand. The channel state between each mobile and the base station is stochastically time-varying and is observed by the mobile prior to transmission. Given the current channel state, a mobile may decide whether to transmit or not, and to determine the transmission power in case of transmission. In this paper, we investigate the properties of the Nash equilibrium of the resulting game in multiuser networks.

We consider a wireless collision channel, shared by a finite number of users who transmit to a common base station. Each user wishes to minimize its average transmission rate (or power investment), subject to minimum throughput demand. The channel quality between each user and the base station is randomly time-varying, and partially observed by the user through Channel State Information (CSI) signals. Assuming that all users employ stationary, CSI-dependent transmission policies, we investigate the properties of the Nash equilibrium of the resulting game between users. We characterize the feasible region of user's throughput demands, and provide lower bounds on the channel capacity that hold both for symmetric and non-symmetric users. Our equilibrium analysis reveals that, when the throughput demands are feasible, there exist exactly two Nash equilibrium points, with one strictly better than the other (in terms of power investment) for each user. We further demonstrate that the performance gap between the two equilibria may be arbitrarily large. This motivates the need for distributed mechanisms that lead to the better equilibrium. To that end, we suggest a simple greedy (best-response) mechanism, and prove convergence to the better equilibrium. Some important stability properties of this mechanism in face of changing user population are derived as well.

Curvature flows have been extensively considered from a deterministic point of view. They have been shown to be useful for a number of applications including crystal growth, flame propagation, and computer vision. In some previous work G. Ben-Arous et al. (2002), we have described a random particle system, evolving on the discretized unit circle, whose profile converges toward the Gauss-Minkowsky transformation of solutions of curve shortening flows initiated by convex curves. The present note shows that this theory may be implemented as a new way of evolving curves and as a possible alternative to level set methods.

We consider the problem of learning to attain multiple goals in a dynamic envi- ronment, which is initially unknown. In addition, the environment may contain arbitrarily varying elements related to actions of other agents or to non-stationary moves of Nature. This problem is modelled as a stochastic (Markov) game between the learning agent and an arbitrary player, with a vector-valued reward function. The objective of the learning agent is to have its long-term average reward vector belong to a given target set. We devise an algorithm for achieving this task, which is based on the theory of approachability for stochastic games. This algorithm com- bines, in an appropriate way, a flnite set of standard, scalar-reward learning algo- rithms. Su–cient conditions are given for the convergence of the learning algorithm to a general target set. The specialization of these results to the single-controller Markov decision problem are discussed as well.

We study a class of noncooperative general topology networks shared by N users. Each user has a given flow which it has to ship from a source to a destination. We consider a class of polynomial link cost functions, adopted originally in the context of road traffic modeling, and show that these costs have appealing properties that lead to predictable and efficient network flows. In particular, we show that the Nash equilibrium is unique, and is moreover efficient, i.e., it coincides with the solution of a corresponding global optimization problem with a single user. These properties make the cost structure attractive for traffic regulation and link pricing in telecommunication networks. We finally discuss the computation of the equilibrium in the special case of the affine cost structure for a topology of parallel links.

Communication networks typically provide a basic best-effort service category, in which resources are shared by concurrent users. As no QoS guarantees are provided, a user will submit to best-effort service only if the expected QoS meets some minimal, user-specific, requirements. This results in an inherent conflict of interest among users, which we capture through a dynamic noncooperative game model and investigate its structure and properties. Specifically, we study the operating points of such systems, i.e., their Nash equilibria. First, we investigate the optimal user strategies, which involve a prediction of the evolving system state, and show that they are of the threshold type. We then establish that a Nash equilibrium point exists and is unique. An algorithmic scheme for computing the Nash equilibrium is provided. In practice, rather than making complex predictions, users typically employ simple decision rules, based on what they learn by experience. Interestingly, it can be shown that the Nash equilibrium of the considered system is a stationary point of such learning schemes. Moreover, we demonstrate that the decisions of users which employ such schemes converge to the Nash equilibrium. Finally, we discuss the implications of the study on network design and management.

Modern communication networks evolve towards integration of guaranteed-performance and best-effort service types. The co-existence of these two service types offers substantial benefits, such as resource sharing between service classes, and the ability of the user to select an appropriate service class according to its individual requirements and preferences. Notwithstanding, such interaction potentially complicates the system behavior, and gives rise to subtle optimization questions, which need to be explored and understood in order to allow efficient network operation. In this paper we address some essential performance and flow control issues associated with such service interactions. We propose a fluid model for session flow, which captures the two interaction mechanisms of resource sharing. In particular, our model incorporates the possibility of session migration, where sessions may shift from best effort to guaranteed performance service due to congestion experienced in the former. Within this model, we analyze the system performance and characterize its steady state behavior. We further show that under certain conditions the system exhibits bistable behavior, where some transient congestion may stir the system from a stable and efficient operating point to an inefficient and congested one, which might persist indefinitely. For the latter case, we propose a call admission control scheme which prevents the system from getting trapped in a congested-type equilibrium, while not interfering with normal system operation.

We consider a communication network that offers multi-class services to multiple types of traffic. Users choose service classes so as to optimize their own performance. The network associates with each traffic type a nominal service class. Optimal prices should provide incentives for the users to assign each traffic type to its nominal service class. We establish necessary and sufficient conditions for the existence of optimal prices and provide an algorithm for their computation. We indicate that optimal prices can tolerate fluctuations in the various parameters. We then devise a distributed algorithm, with which the network can compute optimal prices even when it does not have sufficient knowledge on the traffic characteristics. Next, we consider an extended model which explicitly includes congestion effects. A key factor which emerges here is the amount of traffic at the disposal of each user. We consider the typical cases of individual, social and type optimization, for which we generalize our results.

A communication network shared by several selfish users is considered. Each user seeks to optimize its own performance by controlling the routing of its given flow demand, giving rise to a noncooperative game. The Nash equilibrium of such systems is investigated. For a two-node multiple-link system, the uniqueness of the Nash equilibrium is proved under reasonable convexity conditions. It is shown that this Nash equilibrium point possesses interesting monotonicity properties. For general networks, the uniqueness of the Nash equilibrium is established under various assumptions.>

The authors consider a communication network shared by several selfish users. Each user seeks to optimize its own performance by controlling the routing of its given flow demand, giving rise to a noncooperative game. They investigate the Nash equilibrium of such systems. For a two-node multiple links system, uniqueness of the Nash equilibrium is proven under reasonable convexity conditions. It is shown that this Nash equilibrium point possesses interesting monotonicity properties. For general networks, these convexity conditions are not sufficient for guaranteeing uniqueness, and a counterexample is presented. Nonetheless, uniqueness of the Nash equilibrium for general topologies is established under various assumptions.>