Journal of Artificial Intelligence Resarch: Volume 64の論文一覧

Journal of Artificial Intelligence Resarch Vol. 64 (2019)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。

論文

Fair Allocation of Indivisible Goods to Asymmetric Agents

Fair Allocation of Indivisible Goods to Asymmetric Agents / 非対称エージェントへの不可分財の公平な割り当て

We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee.Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.



我々は、不均等な権利を持つエージェントへの分割不可能な財の公平な割り当てを研究します。公平な割り当ては、分割可能な設定と分割不可能な設定の両方において多くの研究の対象となってきた。我々は、財が分割不可能で、エージェントが不均等な権利を持つ場合に焦点を当てる。この問題は、エージェントが権利に関して対称であると仮定したProcaccia and Wang (2014)の研究の一般化です。Procaccia and Wangは、彼らの設定においてほぼ公平な（定数近似）割り当てが存在することを示しているが、我々の主な結果は彼らの観察とは著しく対照的です。我々は、n人のエージェントがいる場合、権利が必ずしも等しくない場合、どの割り当ても公平な割り当ての1/n近似よりも良いことを保証できないことを示す。さらに、1/n近似を保証するシンプルなアルゴリズムを考案します。2つ目の結果は、各財に対する各エージェントの評価が、公平な配分において各エージェントが受け取りたいと望む合計価値によって制限されるという、問題の制限されたバージョンに対するものです。この仮定は一般性を損なわないように見えるかもしれないが、貪欲アルゴリズムを用いて1/2近似の公平な配分を見つけることができることを示す。最後に、実世界のデータを用いていくつかの実験を行い、実際には公平な配分が存在する可能性が高いことを示す。また、確率的エージェントと確率的アイテムという、問題の2つの確率的変種に対して肯定的な結果を示すことで、実験を裏付ける。

New Approximations for Coalitional Manipulation in Scoring Rules

New Approximations for Coalitional Manipulation in Scoring Rules / スコアリングルールにおける連携操作の新しい近似

We study the problem of coalitional manipulation—where k manipulators try to manipulate an election on m candidates—for any scoring rule, with focus on the Borda protocol. We do so in both the weighted and unweighted settings. For these problems, recent approximation approaches have tried to minimize k, the number of manipulators needed to make some preferred candidate p win (thus assuming that the number of manipulators is not limited in advance). In contrast, we focus on minimizing the score margin of p which is the difference between the maximum score of a candidate and the score of p. We provide algorithms that approximate the optimum score margin, which are applicable to any scoring rule. For the specific case of the Borda protocol in the unweighted setting, our algorithm provides a superior approximation factor for lower values of k.Our methods are novel and adapt techniques from multiprocessor scheduling by carefully rounding an exponentially-large configuration linear program that is solved by using the ellipsoid method with an efficient separation oracle. We believe that such methods could be beneficial in other social choice settings as well.



我々は、ボルダ プロトコルに焦点を当て、任意のスコアリング ルールについて、k人のマニピュレータがm人の候補者による選挙を操作しようとする連合操作の問題を研究します。これは、重み付け設定と重み付けなし設定の両方で行います。これらの問題に対して、最近の近似アプローチは、ある優先候補者pを勝たせるために必要なマニピュレータの数kを最小化しようとしてきました(したがって、マニピュレータの数は事前に制限されていないと仮定します)。対照的に、我々は、候補者の最大スコアとpのスコアの差であるpのスコア マージンを最小化することに焦点を当てています。我々は、任意のスコアリング ルールに適用可能な、最適なスコア マージンを近似するアルゴリズムを提供します。重み付けなし設定のボルダ プロトコルの特定のケースでは、我々のアルゴリズムは、kの値が低い場合に優れた近似係数を提供します。我々の方法は斬新であり、効率的な分離オラクルを使用した楕円体法を使用して解かれる指数関数的に大きな構成の線形計画を慎重に丸めることにより、マルチプロセッサ スケジューリングの手法を応用しています。このような手法は、他の社会的選択の状況においても有益である可能性があると我々は考えています。

A Generalisation of AGM Contraction and Revision to Fragments of First-Order Logic

A Generalisation of AGM Contraction and Revision to Fragments of First-Order Logic / AGM縮約の一般化と一階述語論理の断片への修正

AGM contraction and revision assume an underlying logic that contains propositional logic. Consequently, this assumption excludes many useful logics such as the Horn fragment of propositional logic and most description logics. Our goal in this paper is to generalise AGM contraction and revision to (near-)arbitrary fragments of classical first-order logic. To this end, we first define a very general logic that captures these fragments. In so doing, we make the modest assumptions that a logic contains conjunction and that information is expressed by closed formulas or sentences. The resulting logic is called first-order conjunctive logic or FC logic for short. We then take as the point of departure the AGM approach of constructing contraction functions through epistemic entrenchment, that is the entrenchment-based contraction. We redefine entrenchment-based contraction in ways that apply to any FC logic, which we call FC contraction. We prove a representation theorem showing its compliance with all the AGM contraction postulates except for the controversial recovery postulate. We also give methods for constructing revision functions through epistemic entrenchment which we call FC revision; which also apply to any FC logic. We show that if the underlying FC logic contains tautologies then FC revision complies with all the AGM revision postulates. Finally, in the context of FC logic, we provide three methods for generating revision functions via a variant of the Levi Identity, which we call contraction, withdrawal and cut generated revision, and explore the notion of revision equivalence. We show that withdrawal and cut generated revision coincide with FC revision and so does contraction generated revision under a finiteness condition.



AGMの縮約と修正は、命題論理を含む基礎論理を前提としています。したがって、この前提は、命題論理のホーン断片やほとんどの記述論理など、多くの有用な論理を除外します。本論文の目標は、AGMの縮約と修正を、古典的な一階述語論理の（ほぼ）任意の断片に一般化することです。この目的のために、まずこれらの断片を捉える非常に一般的な論理を定義します。その際、論理には連言が含まれており、情報は閉じた式または文で表現されるという控えめな仮定を立てます。結果として得られる論理は、一階述語論理、または略してFC論理と呼ばれます。次に、認識論的エントレンチメントを通じて縮約関数を構築するAGMアプローチ、すなわちエントレンチメントベースの縮約を出発点とします。エントレンチメントベースの縮約を、あらゆるFC論理に適用できる方法で再定義し、これをFC縮約と呼びます。我々は、議論の的となっている回復公理を除くすべてのAGM縮約公理に準拠していることを示す表現定理を証明します。また、FC修正と呼ぶ認識論的エントレンチメントを通じて修正関数を構築する方法も示します。これは任意のFCロジックにも適用できます。基礎となるFCロジックにトートロジーが含まれている場合、FC修正はすべてのAGM修正公理に準拠することを示します。最後に、FCロジックのコンテキストで、レヴィ恒等式の変形を介して修正関数を生成する3つの方法(縮約、撤退、およびカット生成修正と呼ぶ)を示し、修正同等性の概念を検討します。撤退およびカット生成修正はFC修正と一致し、有限条件の下では縮約生成修正も一致することを示します。

Multi-scale Hierarchical Residual Network for Dense Captioning

Multi-scale Hierarchical Residual Network for Dense Captioning / 稠密なマルチスケール階層的残差ネットワークキャプション作成

Recent research on dense captioning based on the recurrent neural network and the convolutional neural network has made a great progress. However, mapping from an image feature space to a description space is a nonlinear and multimodel task, which makes it difficult for the current methods to get accurate results. In this paper, we put forward a novel approach for dense captioning based on hourglass-structured residual learning. Discriminant feature maps are obtained by incorporating dense connected networks and residual learning in our model. Finally, the performance of the approach on the Visual Genome V1.0 dataset and the region labelled MS-COCO (Microsoft Common Objects in Context) dataset are demonstrated. The experimental results have shown that our approach outperforms most current methods.



近年、リカレントニューラルネットワークと畳み込みニューラルネットワークに基づく高密度キャプション生成の研究は大きく進歩しました。しかし、画像特徴空間から記述空間へのマッピングは非線形かつマルチモデルタスクであるため、現在の方法では正確な結果を得ることが困難です。本稿では、砂時計構造の残差学習に基づく高密度キャプション生成のための新しいアプローチを提案します。識別特徴マップは、高密度接続ネットワークと残差学習をモデルに組み込むことで得られます。最後に、Visual Genome V1.0データセットとMS-COCO (Microsoft Common Objects in Context)データセットでこのアプローチのパフォーマンスを実証します。実験結果は、このアプローチが現在のほとんどの方法よりも優れていることを示しています。

Cost-Based Goal Recognition in Navigational Domains

Cost-Based Goal Recognition in Navigational Domains / ナビゲーション領域におけるコストベースの目標認識

Goal recognition is the problem of determining an agent’s intent by observing her behaviour. Contemporary solutions for general task-planning relate the probability of a goal to the cost of reaching it. We adapt this approach to goal recognition in the strict context of path-planning. We show (1) that a simpler formula provides an identical result to current state-of-the-art in less than half the time under all but one set of conditions. Further, we prove (2) that the probability distribution based on this technique is independent of an agent’s past behaviour and present a revised formula that achieves goal recognition by reference to the agent’s starting point and current location only. Building on this, we demonstrate (3) that a Radius of Maximum Probability (i.e., the distance from a goal within which that goal is guaranteed to be the most probable) can be calculated from relative cost-distances between the candidate goals and a start location, without needing to calculate any actual probabilities. In this extended version of earlier work, we generalise our framework to the continuous domain and discuss our results, including the conditions under which our findings can be generalised back to goal recognition in general task-planning.



目標認識とは、エージェントの行動を観察することでその意図を判断する問題です。一般的なタスク計画に対する現在のソリューションは、目標の確率とそこに到達するコストを関連付けます。私たちはこのアプローチを、厳密なパス計画のコンテキストにおける目標認識に適応させます。我々は、(1)より単純な式により、1つの条件セットを除くすべての条件において、現在の最先端技術と同一の結果を半分以下の時間で得られることを示す。さらに、(2)この手法に基づく確率分布はエージェントの過去の行動とは独立であることを証明し、エージェントの出発点と現在位置のみを参照して目標認識を実現する改訂版の式を提示します。これに基づき、(3)最大確率半径（すなわち、目標からの距離のうち、その目標が最も高い確率であることが保証される距離）を、実際の確率を計算する必要なく、候補目標と出発点間の相対コスト距離から計算できることを示す。この先行研究の拡張版では、我々の枠組みを連続領域に一般化し、我々の発見を一般的なタスク計画における目標認識に一般化できる条件を含め、結果について議論します。

On Inductive Abilities of Latent Factor Models for Relational Learning

On Inductive Abilities of Latent Factor Models for Relational Learning / 関係学習のための潜在因子モデルの帰納的能力について

Latent factor models are increasingly popular for modeling multi-relational knowledge graphs. By their vectorial nature, it is not only hard to interpret why this class of models works so well, but also to understand where they fail and how they might be improved. We conduct an experimental survey of state-of-the-art models, not towards a purely comparative end, but as a means to get insight about their inductive abilities. To assess the strengths and weaknesses of each model, we create simple tasks that exhibit first, atomic properties of binary relations, and then, common inter-relational inference through synthetic genealogies. Based on these experimental results, we propose new research directions to improve on existing models.



潜在因子モデルは、多関係知識グラフのモデリングにおいてますます人気が高まっています。ベクトル的な性質のため、この種のモデルがなぜこれほどうまく機能するのかを解釈するのは困難であるだけでなく、どこで失敗し、どのように改善できるのかを理解することも困難です。私たちは、最先端のモデルを実験的に調査します。これは、純粋に比較するためではなく、それらの帰納的能力についての洞察を得るための手段です。各モデルの長所と短所を評価するために、まず二項関係の原子的特性を示し、次に合成系譜を通して共通の相互関係推論を示す単純なタスクを作成します。これらの実験結果に基づき、既存のモデルを改善するための新たな研究方向を提案します。

Viewpoint: Human-in-the-loop Artificial Intelligence

Viewpoint: Human-in-the-loop Artificial Intelligence / 視点：人間参加型人工知能

Little by little, newspapers are revealing the bright future that Artificial Intelligence (AI) is building. Intelligent machines will help everywhere. However, this bright future may have a possible dark side: a dramatic job market contraction before its unpredictable transformation. Hence, in a near future, large numbers of job seekers may need financial support while catching up with these novel unpredictable jobs. This possible job market crisis has an antidote inside. In fact, the rise of AI is sustained by the biggest knowledge theft of the recent years. Many learning AI machines are extracting knowledge from unaware skilled or unskilled workers by analyzing their interactions. By passionately doing their jobs, many of these workers are shooting themselves in the feet.In this paper, we propose Human-in-the-loop Artificial Intelligence (HitAI) as a fairer paradigm for AI systems. Recognizing that any AI system has humans in the loop, HitAI will reward these aware and unaware knowledge producers with a different scheme: decisions of AI systems generating revenues will repay the legitimate owners of the knowledge used for taking those decisions. As modern Merry Men, HitAI researchers should fight for a fairer Robin Hood Artificial Intelligence that gives back what it steals.This article is part of the special track on AI and Society.



新聞は少しずつ、人工知能（AI）が築き上げている明るい未来を明らかにしています。インテリジェントマシンはあらゆる場所で役立つでしょう。しかし、この明るい未来には、予測不可能な変革の前に、雇用市場が劇的に縮小するという暗い側面があるかもしれません。そのため、近い将来、多くの求職者が、これらの新しい予測不可能な仕事に追いつくために経済的支援を必要とするかもしれません。この潜在的な雇用市場の危機には、内在する解毒剤があります。実際、AIの台頭は、近年の最大の知識窃盗によって支えられています。多くの学習型AIマシンは、無知な熟練労働者または未熟練労働者の相互作用を分析することにより、知識を抽出しています。熱心に仕事をすることで、これらの労働者の多くは自ら足を撃ち抜いています。本稿では、AIシステムのより公平なパラダイムとして、人間参加型人工知能（HitAI）を提案します。あらゆるAIシステムには人間が関与していることを認識し、HitAIは、意識のある知識生産者と意識のない知識生産者に異なる報酬を与えます。収益を生み出すAIシステムの決定は、その決定に使用された知識の正当な所有者に還元されます。現代の陽気な人々として、HitAIの研究者は、盗んだものを返してくれる、より公平なロビンフッド人工知能のために戦うべきです。本稿は、「AIと社会」に関する特別トラックの一部です。

Logical Foundations of Linked Data Anonymisation

Logical Foundations of Linked Data Anonymisation / リンクトデータ匿名化の論理的基礎

The widespread adoption of the Linked Data paradigm has been driven by the increasing demand for information exchange between organisations, as well as by regulations in domains such as health care and governance that require certain data to be published. In this setting, sensitive information is at high risk of disclosure since published data can be often seamlessly linkedwith arbitrary external data sources.In this paper we lay the logical foundations of anonymisation in the context of Linked Data. We consider anonymisations of RDF graphs (and, more generally, relational datasets with labelled nulls) and define notions of policy-compliant and linkage-safe anonymisations. Policy compliance ensures that an anonymised dataset does not reveal any sensitive information as specified by a policy query. Linkage safety ensures that an anonymised dataset remains compliant even if it is linked to (possibly unknown) external datasets available on the Web, thus providing provable protection guarantees against data linkage attacks. We establish the computational complexity of the underpinning decision problems both under the open-world semantics inherent to RDF and under the assumption that an attacker has complete, closed-world knowledge over some parts of the original data.



Linked Dataパラダイムの広範な採用は、組織間の情報交換の需要の高まり、そして医療やガバナンスなどの分野における特定のデータの公開を義務付ける規制によって推進されてきました。このような状況では、公開されたデータは任意の外部データソースとシームレスにリンクされることが多いため、機密情報が漏洩するリスクが高くなります。本稿では、Linked Dataの文脈における匿名化の論理的基礎を構築します。RDFグラフ（およびより一般的には、ラベル付きヌルを持つリレーショナルデータセット）の匿名化を考察し、ポリシーに準拠したリンクセーフな匿名化の概念を定義します。ポリシーコンプライアンスは、匿名化されたデータセットがポリシークエリで指定された機密情報を漏洩しないことを保証します。リンク安全性は、匿名化されたデータセットがWeb上で利用可能な（おそらく未知の）外部データセットにリンクされている場合でも準拠していることを保証し、データリンク攻撃に対する証明可能な保護保証を提供します。RDF固有のオープンワールドセマンティクスと、攻撃者が元のデータの一部に関する完全な閉世界の知識を持っているという仮定の両方の下で、基礎となる意思決定問題の計算複雑性を確立します。

Iterative Local Voting for Collective Decision-making in Continuous Spaces

Iterative Local Voting for Collective Decision-making in Continuous Spaces / 連続空間における集団的意思決定のための反復的局所投票

Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a algorithm called Iterative Local Voting for collective decision-making in this setting. In this algorithm, voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm, with the size of the ball shrinking at a specified rate. We first prove the convergence of this algorithm under appropriate choices of neighborhoods to Pareto optimal solutions with desirable fairness properties in certain natural settings: when the voters’ utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution.We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 2,000 workers, employing neighborhoods defined by various L-Norm balls. We make several observations that inform future implementations of such a procedure.



多くの社会的意思決定問題は、離散的または1次元の対応問題に一般的な投票手法には対応できない高次元連続空間に存在します。これらの問題は通常、選挙を実施する前に離散化されるか、代表者による交渉を通じて決定されます。私たちは、この設定での集団意思決定のために、反復的局所投票と呼ばれるアルゴリズムを提案します。このアルゴリズムでは、投票者が順次サンプリングされ、選択されたノルムのボールによって定義される現在の値のいくつかのローカル近傍内で候補ソリューションを変更するように求められます。ボールのサイズは指定された速度で縮小します。まず、適切な近傍の選択の下で、このアルゴリズムが、特定の自然設定で望ましい公平性を備えたパレート最適ソリューションに収束することを証明します。つまり、投票者の効用が理想的なソリューションからの距離の何らかの形式で表現でき、これらの効用が次元間で加算的に分解可能である場合です。これらのケースの多くでは、社会的福祉を最大化するソリューションへの収束が得られます。次に、さまざまなLノルム ボールによって定義された近傍を使用して、2,000人以上のワーカーでMechanical Turkの米国連邦予算の決定に関するアルゴリズムをテストする実験について説明します。このような手順の将来の実装に役立ついくつかの観察を行います。

Level-0 Models for Predicting Human Behavior in Games

Level-0 Models for Predicting Human Behavior in Games / ゲームにおける人間の行動を予測するためのレベル0モデル

Behavioral game theory seeks to describe the way actual people (as compared to idealized, “rational” agents) act in strategic situations. Our own recent work has identified iterative models, such as quantal cognitive hierarchy, as the state of the art for predicting human play in unrepeated, simultaneous-move games. Iterative models predict that agents reason iteratively about their opponents, building up from a specification of nonstrategic behavior called level-0. A modeler is in principle free to choose any description of level-0 behavior that makes sense for a given setting. However, in practice almost all existing work specifies this behavior as a uniform distribution over actions. In most games it is not plausible that even nonstrategic agents would choose an action uniformly at random, nor that other agents would expect them to do so. A more accurate model for level-0 behavior has the potential to dramatically improve predictions of human behavior, since a substantial fraction of agents may play level-0 strategies directly, and furthermore since iterative models ground all higher-level strategies in responses to the level-0 strategy. Our work considers models of the way in which level-0 agents construct a probability distribution over actions, given an arbitrary game. We considered a large space of alternatives and, in the end, recommend a model that achieved excellent performance across the board: a linear weighting of four binary features, each of which is general in the sense that it can be computed from any normal form game. Adding real-valued variants of the same four features yielded further improvements in performance, albeit with a corresponding increase in the number of parameters needing to be estimated. We evaluated the effects of combining these new level-0 models with several iterative models and observed large improvements in predictive accuracy.



行動ゲーム理論は、現実の人間（理想化された「合理的な」エージェントと比較して）が戦略的な状況においてどのように行動するかを記述しようとするものです。私たち自身の最近の研究では、量子認知階層などの反復モデルが、反復のない同時行動ゲームにおける人間の行動を予測するための最先端のモデルであることが明らかになりました。反復モデルは、エージェントがレベル0と呼ばれる非戦略的行動の仕様に基づいて、対戦相手について反復的に推論することを予測します。モデル作成者は、原則として、与えられた設定において意味のあるレベル0行動の記述を自由に選択できます。しかし、実際には、既存の研究のほとんどすべてが、この行動を行動に対する一様分布として規定しています。ほとんどのゲームでは、非戦略的エージェントでさえ一様ランダムに行動を選択することは考えにくく、また他のエージェントがそうすることを期待することも考えにくいです。レベル0行動のより正確なモデルは、人間の行動予測を劇的に改善する可能性があります。これは、相当数のエージェントがレベル0戦略を直接実行する可能性があり、さらに反復モデルはすべての高レベル戦略をレベル0戦略への応答に基づかせるためです。本研究では、任意のゲームが与えられた場合に、レベル0エージェントが行動の確率分布を構築する方法のモデルを検討します。私たちは広範な選択肢を検討し、最終的に、全般的に優れたパフォーマンスを達成するモデルを推奨しました。それは、4つの2値特徴の線形重み付けであり、各特徴は任意の正規形ゲームから計算できるという意味で汎用的です。同じ4つの特徴の実数値バリアントを追加することで、推定が必要なパラメータの数がそれに応じて増加しましたが、パフォーマンスはさらに向上しました。これらの新しいレベル0モデルを複数の反復モデルと組み合わせた効果を評価し、予測精度が大幅に向上することを確認しました。

A Sampling Approach for Proactive Project Scheduling under Generalized Time-dependent Workability Uncertainty

A Sampling Approach for Proactive Project Scheduling under Generalized Time-dependent Workability Uncertainty / 一般化された時間依存作業性不確実性下におけるプロアクティブ・プロジェクト・スケジューリングのためのサンプリング・アプローチ

In real-world project scheduling applications, activity durations are often uncertain. Proactive scheduling can effectively cope with the duration uncertainties, by generating robust baseline solutions according to a priori stochastic knowledge. However, most of the existing proactive approaches assume that the duration uncertainty of an activity is not related to its scheduled start time, which may not hold in many real-world scenarios. In this paper, we relax this assumption by allowing the duration uncertainty to be time-dependent, which is caused by the uncertainty of whether the activity can be executed on each time slot. We propose a stochastic optimization model to find an optimal Partial-order Schedule (POS) that minimizes the expected makespan. This model can cover both the time-dependent uncertainty studied in this paper and the traditional time-independent duration uncertainty. To circumvent the underlying complexity in evaluating a given solution, we approximate the stochastic optimization model based on Sample Average Approximation (SAA). Finally, we design two efficient branch-and-bound algorithms to solve the NP-hard SAA problem. Empirical evaluation confirms that our approach can generate high-quality proactive solutions for a variety of uncertainty distributions.



現実世界のプロジェクトスケジューリングアプリケーションでは、アクティビティの所要期間はしばしば不確実です。プロアクティブスケジューリングは、事前確率的知識に基づいて堅牢なベースラインソリューションを生成することで、所要期間の不確実性に効果的に対処できます。しかし、既存のプロアクティブアプローチの多くは、アクティビティの所要期間の不確実性がその予定開始時刻とは無関係であると仮定していますが、これは多くの現実世界のシナリオでは当てはまらない可能性があります。本稿では、アクティビティが各時間帯に実行できるかどうかの不確実性によって引き起こされる、所要期間の不確実性が時間に依存することを許容することで、この仮定を緩和します。期待メイクスパンを最小化する最適な半順序スケジュール（POS）を見つけるための確率的最適化モデルを提案します。このモデルは、本稿で検討した時間依存の不確実性と、従来の時間に依存しない所要期間の不確実性の両方をカバーできます。与えられたソリューションを評価する際の根本的な複雑さを回避するため、サンプル平均近似（SAA）に基づいて確率的最適化モデルを近似します。最後に、NP困難なSAA問題を解くための2つの効率的な分枝限定アルゴリズムを設計します。実証的評価により、本手法は様々な不確実性分布に対して高品質なプロアクティブ解を生成できることが確認されました。

Revisiting CFR+ and Alternating Updates

Revisiting CFR+ and Alternating Updates / CFR+と交互更新の再考

The CFR+ algorithm for solving imperfect information games is a variant of the popular CFR algorithm, with faster empirical performance on a range of problems. It was introduced with a theoretical upper bound on solution error, but subsequent work showed an error in one step of the proof. We provide updated proofs to recover the original bound.



不完全情報ゲームを解くためのCFR+アルゴリズムは、広く普及しているCFRアルゴリズムの派生であり、様々な問題においてより高速な実証的性能を示します。このアルゴリズムは、解の誤差に関する理論的な上限値とともに導入されましたが、その後の研究では証明の1ステップに誤りがあることが示されました。本研究では、元の上限値を回復するための更新された証明を提供します。

Dynamic Controllability of Controllable Conditional Temporal Problems with Uncertainty

Dynamic Controllability of Controllable Conditional Temporal Problems with Uncertainty / 不確実性を伴う制御可能な条件付き時間的問題の動的制御可能性

Dynamic Controllability (DC) of a Simple Temporal Problem with Uncertainty (STPU) uses a dynamic decision strategy, rather than a fixed schedule, to tackle temporal uncertainty. We extend this concept to the Controllable Conditional Temporal Problem with Uncertainty (CCTPU), which extends the STPU by conditioning temporal constraints on the assignment of controllable discrete variables. We define dynamic controllability of a CCTPU as the existence of a strategy that decides on both the values of discrete choice variables and the scheduling of controllable time points dynamically. This contrasts with previous work, which made a static assignment of choice variables and dynamic decisions over time points only. We propose an algorithm to find such a fully dynamic strategy. The algorithm computes the “envelope” of outcomes of temporal uncertainty in which a particular assignment of discrete variables is feasible, and aggregates these over all choices. When an aggregated envelope covers all uncertain situations of the CCTPU, the problem is dynamically controllable. However, the algorithm is complete only under certain assumptions. Experiments on an existing set of CCTPU benchmarks show that there are cases in which making both discrete and temporal decisions dynamically it is feasible to satisfy the problem constraints while assigning the discrete variables statically it is not.



不確実性を伴う単純時間問題（STPU）の動的可制御性（DC）は、時間的不確実性に対処するために、固定スケジュールではなく動的な決定戦略を用います。本研究ではこの概念を、不確実性を伴う制御可能な条件付き時間問題（CCTPU）に拡張します。CCTPUは、制御可能な離散変数の割り当てに時間的制約を条件付けることでSTPUを拡張します。CCTPUの動的可制御性を、離散選択変数の値と制御可能な時点のスケジュールの両方を動的に決定する戦略の存在と定義します。これは、選択変数の静的割り当てと時点に基づく動的な決定のみを行った先行研究とは対照的です。本研究では、このような完全に動的な戦略を見つけるためのアルゴリズムを提案します。このアルゴリズムは、離散変数の特定の割り当てが実行可能な時間的不確実性の結果の「エンベロープ」を計算し、これをすべての選択肢にわたって集約します。集約されたエンベロープがCCTPUのすべての不確実な状況をカバーする場合、問題は動的に制御可能になります。ただし、このアルゴリズムは特定の仮定の下でのみ完全です。既存のCCTPUベンチマークを用いた実験では、離散変数と時間的決定の両方を動的に行うことで問題の制約を満たすことが可能でありながら、離散変数を静的に割り当てると満たせないケースがあることが示されています。

Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity

Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity / 目的地不確実性下における暗黙的に協調されたマルチエージェント経路探索：成功保証と計算複雑性

In multi-agent path finding (MAPF), it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication. Furthermore, we will analyze what the computational costs associated with such a coordination regime are. As it turns out, guarantees can be given assuming that the agents are of a certain type. However, the implied computational costs are quite severe. In the distributed setting, we either have to solve a sequence of NP-complete problems or have to tolerate exponentially longer executions. In the setting with destination uncertainty, bounded plan existence becomes PSPACE-complete. This clearly demonstrates the value of communicating about plans before execution starts.



マルチエージェント経路探索（MAPF）では、通常、計画は中央集権的に行われ、エージェントの目的地は共通知識であると仮定されます。本研究では、これらの仮定を放棄し、エージェントが通信なしに暗黙的に調整された計画を用いてそれぞれの目的地に到達することが保証される条件を解析します。さらに、このような調整体制に伴う計算コストがどの程度になるか解析します。結果として、エージェントが特定のタイプであると仮定すれば、保証を与えることができます。しかし、暗黙の計算コストは​​非常に高くなります。分散環境では、NP完全問題のシーケンスを解くか、指数関数的に長い実行時間を許容するかのいずれかが必要になります。目的地が不確実な環境では、限定された計画の存在はPSPACE完全になります。これは、実行開始前に計画について通信することの価値を明確に示しています。

AI Generality and Spearman’s Law of Diminishing Returns

AI Generality and Spearman’s Law of Diminishing Returns / AIの一般性とスピアマンの収穫逓減の法則

Many areas of AI today use benchmarks and competitions with larger and wider sets of tasks. This tries to deter AI systems (and research effort) from specialising to a single task, and encourage them to be prepared to solve previously unseen tasks. It is unclear, however, whether the methods with best performance are actually those that are most general and, in perspective, whether the trend moves towards more general AI systems. This question has a striking similarity with the analysis of the so-called positive manifold and general factors in the area of human intelligence. In this paper, we first show how the existence of a manifold (positive average pairwise task correlation) can also be analysed in AI, and how this relates to the notion of agent generality, from the individual and the populational points of view. From the populational perspective, we analyse the following question: is this manifold correlation higher for the most or for the least able group of agents? We contrast this analysis with one of the most controversial issues in human intelligence research, the so-called Spearman’s Law of Diminishing Returns (SLODR), which basically states that the relevance of a general factor diminishes for most able human groups. We perform two empirical studies on these issues in AI. We analyse the results of the 2015 general video game AI (GVGAI) competition, with games as tasks and “controllers” as agents, and the results of a synthetic setting, with modified elementary cellular automata (ECA) rules as tasks and simple interactive programs as agents. In both cases, we see that SLODR doesnot appear. The data, and the use of just two scenarios, does not clearly support the reverse either, a Universal Law of Augmenting Returns (ULOAR), but calls for more experiments on this question.



今日のAIの多くの分野では、より大規模で幅広いタスクセットを用いたベンチマークやコンペティションが用いられています。これは、AIシステム（および研究努力）が単一のタスクに特化することを抑制し、これまで未知のタスクを解決できるように準備することを促しています。しかし、最高のパフォーマンスを示す手法が実際に最も汎用的な手法であるかどうか、そして将来的には、AIシステムがより汎用化される傾向にあるかどうかは不明です。この問題は、人間の知能分野におけるいわゆる正の多様体因子と一般因子の分析と顕著な類似性を持っています。本稿ではまず、AIにおいて多様体（正の平均ペアワイズタスク相関）の存在がどのように分析できるか、そしてこれが個人および集団の観点からエージェントの一般性の概念とどのように関連するかを示します。集団の観点からは、この多様体相関は、最も能力の高いエージェントのグループで高いのか、それとも最も能力の低いエージェントのグループで高いのかという問題を分析します。この分析を、人間の知能研究で最も議論の多い問題の1つである、いわゆるスピアマンの収穫逓減の法則（SLODR）と対比させます。これは基本的に、一般因子の関連性はほとんどの能力のある人間グループでは減少するというものです。私たちはAIにおけるこれらの問題について、2つの実証研究を行います。2015年の一般ビデオゲームAI（GVGAI）コンペティションの結果（ゲームをタスク、「コントローラー」をエージェントとする）と、修正された基本セルオートマトン（ECA）ルールをタスク、単純な対話型プログラムをエージェントとする合成設定の結果を分析した。どちらの場合も、SLODRは現れない。データと、わずか2つのシナリオの使用では、逆の普遍的増加収支法則（ULOAR）を明確に支持するものではなく、この問題についてはさらなる実験が必要です。

Rank Pruning for Dominance Queries in CP-Nets

Rank Pruning for Dominance Queries in CP-Nets / CPネットにおける支配クエリのためのランク・プルーニング

Conditional preference networks (CP-nets) are a graphical representation of a person’s (conditional) preferences over a set of discrete features. In this paper, we introduce a novel method of quantifying preference for any given outcome based on a CP-net representation of a user’s preferences. We demonstrate that these values are useful for reasoning about user preferences. In particular, they allow us to order (any subset of) the possible outcomes in accordance with the user’s preferences. Further, these values can be used to improve the efficiency of outcome dominance testing. That is, given a pair of outcomes, we can determine which the user prefers more efficiently. Through experimental results, we show that this method is more effective than existing techniques for improving dominance testing efficiency. We show that the above results also hold for CP-nets that express indifference between variable values.



条件付き選好ネットワーク（CPネット）は、離散的な特徴の集合に対する個人の（条件付き）選好をグラフィカルに表現したものです。本稿では、ユーザーの選好をCPネットで表現することにより、任意の結果に対する選好を定量化する新しい手法を紹介します。これらの値は、ユーザーの選好を推論する上で有用であることを示します。特に、これらの値を用いることで、可能性のある結果（の任意のサブセット）をユーザーの選好に従って順序付けることができます。さらに、これらの値は、結果の優位性テストの効率を向上させるために使用できます。つまり、一対の結果が与えられた場合、ユーザーがどちらをより効率的に選好するかを判断できます。実験結果から、この手法は、優位性テストの効率を向上させる既存の手法よりも効果的であることを示します。上記の結果は、変数値間の無差別性を表現するCPネットにも当てはまることを示します。

Computing and Explaining Query Answers over Inconsistent DL-Lite Knowledge Bases

Computing and Explaining Query Answers over Inconsistent DL-Lite Knowledge Bases / 矛盾するDL-Lite知識ベースにおけるクエリ回答の計算と説明

Several inconsistency-tolerant semantics have been introduced for querying inconsistent description logic knowledge bases. The first contribution of this paper is a practical approach for computing the query answers under three well-known such semantics, namely the AR, IAR and brave semantics, in the lightweight description logic DL-LiteR. We show that query answering under the intractable AR semantics can be performed efficiently by using IAR and brave semantics as tractable approximations and encoding the AR entailment problem as a propositional satisfiability (SAT) problem. The second issue tackled in this work is explaining why a tuple is a (non-)answer to a query under these semantics. We define explanations for positive and negative answers under the brave, AR and IAR semantics. We then study the computational properties of explanations in DL-LiteR. For each type of explanation, we analyze the data complexity of recognizing (preferred) explanations and deciding if a given assertion is relevant or necessary. We establish tight connections between intractable explanation problems and variants of SAT, enabling us to generate explanations by exploiting solvers for Boolean satisfaction and optimization problems. Finally, we empirically study the efficiency of our query answering and explanation framework using a benchmark we built upon the well-established LUBM benchmark.



矛盾した記述論理知識ベースを照会するために、いくつかの矛盾を許容するセマンティクスが導入されています。本論文の最初の貢献は、軽量記述論理DL-LiteRにおいて、よく知られている3つの意味論、すなわちAR、IAR、およびbrave意味論の下でのクエリ回答を計算するための実際的なアプローチです。扱いにくいAR意味論の下でのクエリ回答は、IARおよびbrave意味論を扱いやすい近似として使用し、AR含意問題を命題充足可能性(SAT)問題としてエンコードすることで効率的に実行できることを示します。本研究で取り組む2番目の問題は、これらの意味論の下でタプルがクエリに対する(非)回答である理由を説明することです。brave、AR、およびIAR意味論の下での肯定回答と否定回答の説明を定義します。次に、DL-LiteRにおける説明の計算特性を検討します。各説明タイプについて、(推奨)説明を認識し、特定のアサーションが関連性があるか必要であるかを判断するためのデータ複雑性を解析します。我々は、解決困難な説明問題とSATの変種との密接な関連性を確立し、ブール充足問題および最適化問題のソルバーを活用して説明を生成することを可能にします。最後に、確立されたLUBMベンチマークに基づいて構築したベンチマークを用いて、クエリ応答および説明フレームワークの効率性を実証的に検証します。

A Survey on Transfer Learning for Multiagent Reinforcement Learning Systems

A Survey on Transfer Learning for Multiagent Reinforcement Learning Systems / マルチエージェント強化学習システムのための転移学習に関するサーベイ

Multiagent Reinforcement Learning (RL) solves complex tasks that require coordination with other agents through autonomous exploration of the environment. However, learning a complex task from scratch is impractical due to the huge sample complexity of RL algorithms. For this reason, reusing knowledge that can come from previous experience or other agents is indispensable to scale up multiagent RL algorithms. This survey provides a unifying view of the literature on knowledge reuse in multiagent RL. We define a taxonomy of solutions for the general knowledge reuse problem, providing a comprehensive discussion of recent progress on knowledge reuse in Multiagent Systems (MAS) and of techniques for knowledge reuse across agents (that may be actuating in a shared environment or not). We aim at encouraging the community to work towards reusing all the knowledge sources available in a MAS. For that, we provide an in-depth discussion of current lines of research and open questions.



マルチエージェント強化学習（RL）は、環境を自律的に探索することで、他のエージェントとの協調を必要とする複雑なタスクを解決します。しかし、RLアルゴリズムのサンプル数が非常に多いため、複雑なタスクをゼロから学習することは現実的ではありません。そのため、マルチエージェントRLアルゴリズムをスケールアップするには、過去の経験や他のエージェントから得られる知識の再利用が不可欠です。本調査は、マルチエージェントRLにおける知識再利用に関する文献の統一的な見解を提供します。我々は、一般的な知識再利用問題に対する解決策の分類を定義し、マルチエージェントシステム（MAS）における知識再利用に関する最近の進歩と、エージェント間（共有環境で動作するかどうかは問わない）での知識再利用技術について包括的に議論します。私たちは、MASで利用可能なすべての知識源を再利用するためのコミュニティの取り組みを促進することを目指しています。そのために、現在の研究分野と未解決の問題について、詳細な議論を提供します。

Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm

Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm / 分散ギブス：線形空間サンプリングに基づくDCOPアルゴリズム

Researchers have used distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. Very recently, Ottens et al. proposed a promising new approach to solve DCOPs that is based on confidence bounds via their Distributed UCT (DUCT) sampling-based algorithm. Unfortunately, its memory requirement per agent is exponential in the number of agents in the problem, which prohibits it from scaling up to large problems. Thus, in this article, we introduce two new sampling-based DCOP algorithms called Sequential Distributed Gibbs (SD-Gibbs) and Parallel Distributed Gibbs (PD-Gibbs). Both algorithms have memory requirements per agent that is linear in the number of agents in the problem. Our empirical results show that our algorithms can find solutions that are better than DUCT, run faster than DUCT, and solve some large problems that DUCT failed to solve due to memory limitations.



研究者たちは、分散制約最適化問題(DCOP)を使用して、さまざまなマルチエージェント調整およびリソース割り当て問題をモデル化してきました。ごく最近、Ottensらは、分散UCT (DUCT)サンプリングベースのアルゴリズムによる信頼限界に基づく、DCOPを解決するための有望な新しいアプローチを提案しました。残念ながら、エージェントあたりのメモリ要件は問題内のエージェント数に対して指数関数的に増加するため、大規模な問題に拡張することができません。そこで、この記事では、Sequential Distributed Gibbs (SD-Gibbs)とParallel Distributed Gibbs (PD-Gibbs)という2つの新しいサンプリングベースのDCOPアルゴリズムを紹介します。どちらのアルゴリズムも、エージェントあたりのメモリ要件は問題内のエージェント数に対して線形です。実験結果では、私たちのアルゴリズムはDUCTよりも優れたソリューションを見つけられ、DUCTよりも高速に実行され、メモリ制限のためにDUCTが解決できなかったいくつかの大規模な問題を解決できることが示されています。

Polynomial and Exponential Bounded Logic Programs with Function Symbols: Some New Decidable Classes

Polynomial and Exponential Bounded Logic Programs with Function Symbols: Some New Decidable Classes / 関数シンボルを含む多項式および指数有界論理プログラム：いくつかの新しい決定可能クラス

A logic program with function symbols is called finitely ground if there is a finite propositional logic program whose stable models are exactly the same as the stable models of this program. Finite groundability is an important property for logic programs with function symbols because it makes feasible to compute such programs’ stable models using traditional ASP solvers. In this paper, we introduce new decidable classes of finitely ground programs called poly-bounded and k-EXP-bounded programs, which, to the best of our knowledge, strictly contain all other decidable classes of finitely ground programs discovered so far in the literature. We also study the relevant complexity properties for these classes of programs. We prove that the membership complexities for poly-bounded and k-EXP-bounded programs are EXPTIME-complete and (k+1)-EXPTIME-complete, respectively.



関数記号を含む論理プログラムは、その安定モデルがこのプログラムの安定モデルと全く同じである有限命題論理プログラムが存在する場合、有限基底であると呼ばれます。有限基底可能性は、関数記号を含む論理プログラムにとって重要な特性です。なぜなら、これにより、従来のASPソルバーを用いてそのようなプログラムの安定モデルを計算することが可能になるからです。本稿では、我々は、多境界プログラムおよびk-EXP境界プログラムと呼ばれる有限基底プログラムの新しい決定可能クラスを導入します。これらのクラスは、我々の知る限り、文献でこれまでに発見された他のすべての有限基底プログラムの決定可能クラスを厳密に含みます。また、これらのプログラムクラスの関連する複雑性特性についても検討します。我々は、多境界プログラムおよびk-EXP境界プログラムの帰属複雑性が、それぞれEXPTIME完全および(k+1)-EXPTIME完全であることを証明するものとします。

Modeling and Planning with Macro-Actions in Decentralized POMDPs

Modeling and Planning with Macro-Actions in Decentralized POMDPs / 分散型におけるマクロアクションを用いたモデリングとプランニングPOMDP

Decentralized partially observable Markov decision processes (Dec-POMDPs) are general models for decentralized multi-agent decision making under uncertainty. However, they typically model a problem at a low level of granularity, where each agent’s actions are primitive operations lasting exactly one time step. We address the case where each agent has macro-actions: temporally extended actions that may require different amounts of time to execute. We model macro-actions as options in a Dec-POMDP, focusing on actions that depend only on information directly available to the agent during execution. Therefore, we model systems where coordination decisions only occur at the level of deciding which macro-actions to execute. The core technical difficulty in this setting is that the options chosen by each agent no longer terminate at the same time. We extend three leading Dec-POMDP algorithms for policy generation to the macro-action case, and demonstrate their effectiveness in both standard benchmarks and a multi-robot coordination problem. The results show that our new algorithms retain agent coordination while allowing high-quality solutions to be generated for significantly longer horizons and larger state-spaces than previous Dec-POMDP methods. Furthermore, in the multi-robot domain, we show that, in contrast to most existing methods that are specialized to a particular problem class, our approach can synthesize control policies that exploit opportunities for coordination while balancing uncertainty, sensor information, and information about other agents.



分散型部分観測マルコフ決定プロセス(Dec-POMDP)は、不確実性下での分散型マルチエージェント意思決定の一般的なモデルです。しかし、これらのモデルは通常、粒度が低いレベルで問題をモデル化し、各エージェントの行動は正確に1タイムステップで実行される基本操作です。本稿では、各エージェントがマクロアクション（実行に異なる時間を要する可能性のある、時間的に拡張された行動）を持つケースを取り上げます。マクロアクションはDec-POMDPのオプションとしてモデル化され、実行時にエージェントが直接利用できる情報のみに依存する行動に焦点を当てます。したがって、調整の決定はどのマクロアクションを実行するかを決定するレベルでのみ行われるシステムをモデル化します。この設定における中心的な技術的難しさは、各エージェントが選択したオプションが同時に終了しなくなることです。本稿では、ポリシー生成のための主要な3つのDec-POMDPアルゴリズムをマクロアクションケースに拡張し、標準ベンチマークとマルチロボット調整問題の両方でその有効性を実証します。結果は、新しいアルゴリズムがエージェントの調整を維持しながら、従来のDec-POMDP手法よりもはるかに長い期間とより大きな状態空間で高品質のソリューションを生成できることを示しています。さらに、マルチロボット領域では、特定の問題クラスに特化した既存のほとんどの方法とは対照的に、私たちのアプローチは、不確実性、センサー情報、および他のエージェントに関する情報のバランスを取りながら、調整の機会を活用する制御ポリシーを合成できることを示します。

Pitfalls and Best Practices in Algorithm Configuration

Pitfalls and Best Practices in Algorithm Configuration / アルゴリズム設定における落とし穴とベストプラクティス

Good parameter settings are crucial to achieve high performance in many areas of artificial intelligence (AI), such as propositional satisfiability solving, AI planning, scheduling, and machine learning (in particular deep learning). Automated algorithm configuration methods have recently received much attention in the AI community since they replace tedious, irreproducible and error-prone manual parameter tuning and can lead to new state-of-the-art performance. However, practical applications of algorithm configuration are prone to several (often subtle) pitfalls in the experimental design that can render the procedure ineffective. We identify several common issues and propose best practices for avoiding them. As one possibility for automatically handling as many of these as possible, we also propose a tool called GenericWrapper4AC.



人工知能(AI)の多くの分野、例えば命題充足可能性解決、AIプランニング、スケジューリング、機械学習(特にディープラーニング)などにおいて、高性能を達成するには適切なパラメータ設定が不可欠です。自動化されたアルゴリズム設定手法は、面倒で再現性がなくエラーが発生しやすい手動のパラメータ調整に代わるものとして、AIコミュニティで近年大きな注目を集めています。しかし、アルゴリズム設定の実際の応用では、実験設計においていくつかの(しばしば微妙な)落とし穴に陥りやすく、手順が効果的でなくなる可能性があります。私たちはいくつかの一般的な問題を特定し、それらを回避するためのベストプラクティスを提案します。これらの問題を可能な限り自動的に処理するための1つの可能性として、GenericWrapper4ACと呼ばれるツールも提案します。

Negotiable Votes

Negotiable Votes / 交渉可能な投票

We study voting games on binary issues, where voters hold an objective over the outcome of the collective decision and are allowed, before the vote takes place, to negotiate their ballots with the other participants. We analyse the voters’ rational behaviour in the resulting two-phase game when ballots are aggregated via non-manipulable rules and, more specifically, quota rules. We show under what conditions undesirable equilibria can be removed and desirable ones sustained as a consequence of the pre-vote phase.



私たちは、投票者が集団的決定の結果に対して目的を持ち、投票が行われる前に他の参加者と投票について交渉することが許される、2値問題に関する投票ゲームを研究します。我々は、操作不可能なルール、より具体的にはクォータルールによって投票が集約される結果として生じる2段階ゲームにおける投票者の合理的行動を分析します。我々は、事前投票段階の結果として、どのような条件下で望ましくない均衡が排除され、望ましい均衡が維持されるかを示す。

Conditional Simple Temporal Networks with Uncertainty and Resources

Conditional Simple Temporal Networks with Uncertainty and Resources / 不確実性とリソースを考慮した条件付き単純時系列ネットワーク

Conditional simple temporal networks with uncertainty (CSTNUs) allow for the representation of temporal plans subject to both conditional constraints and uncertain durations.   Dynamic controllability (DC) of CSTNUs ensures the existence of an execution strategy able to execute the network in real time (i.e., scheduling the time points under control) depending on how these two uncontrollable parts behave. However, CSTNUs do not deal with resources. In this paper, we define conditional simple temporal networks with uncertainty and resources (CSTNURs) by injecting resources and runtime resource constraints (RRCs) into the specification.  Resources are mandatory for executing the time points and their availability is represented through temporal expressions, whereas RRCs restrict resource availability by further temporal constraints among resources.We provide a fully-automated encoding to translate any CSTNUR into an equivalent timed game automaton in polynomial time for a sound and complete DC-checking.



不確実性を伴う条件付き単純時相ネットワーク（CSTNU）は、条件付き制約と不確実な期間の両方を条件とする時相プランの表現を可能にします。CSTNUの動的制御可能性（DC）は、これら2つの制御不能な部分の挙動に応じて、ネットワークをリアルタイムで実行できる（つまり、制御下で時点をスケジュールする）実行戦略の存在を保証します。しかし、CSTNUはリソースを扱いません。本稿では、リソースと実行時リソース制約（RRC）を仕様に組み込むことで、不確実性とリソースを伴う条件付き単純時相ネットワーク（CSTNUR）を定義します。リソースはタイムポイントを実行するために必須であり、その可用性は時間的な表現によって表されますが、RRCはリソース間のさらなる時間的制約によってリソースの可用性を制限します。健全で完全なDCチェックのために、任意のCSTNURを多項式時間で同等の時間付きゲーム オートマトンに変換する、完全に自動化されたエンコーディングを提供します。

Using Collective Behavior of Coupled Oscillators for Solving DCOP

Using Collective Behavior of Coupled Oscillators for Solving DCOP / 結合振動子の集団的行動を用いたDCOPの解決

The distributed constraint optimization problem (DCOP) has emerged as one of the most promising coordination techniques in multiagent systems. However, because DCOP is known to be NP-hard, the existing DCOP techniques are often unsuitable for large-scale applications, which require distributed and scalable algorithms to deal with severely limited computing and communication. In this paper, we present a novel approach to provide approximate solutions for large-scale, complex DCOPs. This approach introduces concepts of synchronization of coupled oscillators for speeding up the convergence process towards high-quality solutions. We propose a new anytime local search DCOP algorithm, called Coupled Oscillator OPTimization (COOPT), which amounts to iteratively solving a DCOP by agents exchanging local information that brings them to a consensus. We empirically evaluate COOPT on constraint networks involving hundreds of variables with different topologies, domains, and densities. Our experimental results demonstrate that COOPT outperforms other incomplete state-of-the-art DCOP algorithms, especially in terms of the agents’ communication cost and solution quality.



分散制約最適化問題(DCOP)は、マルチエージェントシステムにおける最も有望な調整手法の1つとして浮上しています。しかし、DCOPはNP困難であることが知られているため、既存のDCOP手法は、厳しく制限されたコンピューティングと通信に対処するために分散型でスケーラブルなアルゴリズムを必要とする大規模アプリケーションには不向きです。本稿では、大規模で複雑なDCOPの近似解を提供するための新しいアプローチを紹介します。このアプローチでは、高品質のソリューションに向けた収束プロセスを高速化するために、結合発振器の同期の概念を導入します。私たちは、結合発振器最適化(COOPT)と呼ばれる、いつでも局所探索が可能な新しいDCOPアルゴリズムを提案します。これは、エージェントが局所情報を交換して合意に至ることで、DCOPを反復的に解くことになります。私たちは、異なるトポロジ、ドメイン、密度を持つ数百の変数を含む制約ネットワークでCOOPTを経験的に評価します。実験結果は、COOPTが他の不完全な最先端のDCOPアルゴリズムよりも、特にエージェントの通信コストとソリューションの品質の点で優れていることを示しています。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 64 (2019)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧