In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

Q: Potential games and decentralised partially observable MDPs (Dec–POMDPs) are two commonly used models of multi–agent interaction, for static optimisation and sequential decision– making settings, respectively. In this paper we introduce filtered fictitious play for solving repeated potential games in which each player’s observations of others’ actions are perturbed by random noise, and use this algorithm to construct an online learning method for solving Dec–POMDPs. Specifically, we prove that noise in observations prevents standard fictitious play from converging to Nash equilibrium in potential games, which also makes fictitious play impractical for solving Dec–POMDPs. To combat this, we derive filtered fictitious play, and provide conditions under which it converges to a Nash equilibrium in potential games with noisy observations. We then use filtered fictitious play to construct a solver for Dec–POMDPs, and demonstrate our new algorithm’s performance in a box pushing problem. Our results show that we consistently outperform the state–of–the–art Dec– POMDP solver by an average of 100% across the range of noise in the observation function.

A: Filtered Fictitious Play for Perturbed Observation Potential Games and Decentralised POMDPs
****
Q: Path planning for multiple robots is well studied in the AI and robotics communities. For a given discretized environment, robots need to find collision-free paths to a set of specified goal locations. Robots can be fully anonymous, non-anonymous, or organized in groups. Although powerful solvers for this abstract problem exist, they make simplifying assumptions by ignoring kinematic constraints, making it difficult to use the resulting plans on actual robots. In this paper, we present a solution which takes kinematic constraints, such as maximum velocities, into account, while guaranteeing a user-specified minimum safety distance between robots. We demonstrate our approach in simulation and on real robots in 2D and 3D environments.

A: Path Planning With Kinematic Constraints For Robot Groups
****
Q: We consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x1 . . . xn is the sum of terms over intervals [i, j] where each term is non-zero only if the substring xi . . . xj equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively O(nL), O(nL`max) and O(nLmin{|D|, log(`max+1)}) where L is the combined length of input patterns, `max is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of [Ye et al. NIPS 2009] whose complexities are respectively O(nL|D|), O ( n|Γ|L`max ) and O(nL|D|), where |Γ| is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights. This paper addresses the sequence labeling (or the sequence tagging) problem: given an observation z (which is usually a sequence of n values), infer labeling x = x1 . . . xn where each variable xi takes values in some finite domain D. Such problem appears in many domains such as text and speech analysis, signal analysis, and bioinformatics. One of the most successful approaches for tackling the problem is the Hidden Markov Model (HMM). The kth order HMM is given by the probability distribution p(x|z) = 1 Z exp{−E(x|z)} with the energy function E(x|z) = ∑ i∈[1,n] ψi(xi, zi) + ∑ (i,j)∈Ek ψij(xi:j) (1) where Ek = {(i, i+ k) | i ∈ [1, n− k]} and xi:j = xi . . . xj is the substring of x from i to j. A popular generalization is the Conditional Random Field model [3] that allows all terms to depend on the full observation z: E(x|z) = ∑ i∈[1,n] ψi(xi, z) + ∑ (i,j)∈Ek ψij(xi:j , z) (2) A preliminary version of this paper appeared in Proceedings of the 30th International Conference on Machine Learning (ICML), 2013 [8]. This work was partially supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160. 1 ar X iv :1 21 0. 05 08 v5 [ cs .L G ] 2 0 Ja n 20 17 We study a particular variant of this model called a pattern-based CRF. It is defined via

A:
Inference algorithms for pattern-based CRFs on sequence data
****