Interpolable Formulas in Equilibrium Logic and Answer Set Programming
均衡論理と解答集合プログラミングにおける補間可能な公式
Interpolation is an important property of classical and many non-classical logics that has been shown to have interesting applications in computer science and AI. Here we study the Interpolation Property for the the non-monotonic system of equilibrium logic, establishing weaker or stronger forms of interpolation depending on the precise interpretation of the inference relation. These results also yield a form of interpolation for ground logic programs under the answer sets semantics. For disjunctive logic programs we also study the property of uniform interpolation that is closely related to the concept of variable forgetting. The first-order version of equilibrium logic has analogous Interpolation properties whenever the collection of equilibrium models is (first-order) definable. Since this is the case for so-called safe programs and theories, it applies to the usual situations that arise in practical answer set programming.
補間は、古典論理および多くの非古典論理の重要な特性であり、コンピュータサイエンスとAIにおいて興味深い応用があることが示されています。本稿では、均衡論理の非単調システムの補間特性を研究し、推論関係の正確な解釈に応じて、より弱いまたはより強い形式の補間を確立します。これらの結果はまた、解答集合意味論の下での基底論理プログラムのための補間の一形態をもたらす。選言論理プログラムについては、変数忘却の概念に密接に関連する一様補間の特性も研究します。平衡論理の一次バージョンは、平衡モデルの集合が（一次）定義可能である場合、類似の補間特性を持ちます。これはいわゆる安全なプログラムや理論に当てはまるため、実際の解答セットプログラミングで発生する通常の状況に適用されます。
Scheduling Bipartite Tournaments to Minimize Total Travel Distance
総移動距離を最小化する二部トーナメントのスケジューリング
In many professional sports leagues, teams from opposing leagues/conferences compete against one another, playing inter-league games. This is an example of a bipartite tournament. In this paper, we consider the problem of reducing the total travel distance of bipartite tournaments, by analyzing inter-league scheduling from the perspective of discrete optimization. This research has natural applications to sports scheduling, especially for leagues such as the National Basketball Association (NBA) where teams must travel long distances across North America to play all their games, thus consuming much time, money, and greenhouse gas emissions.We introduce the Bipartite Traveling Tournament Problem (BTTP), the inter-league variant of the well-studied Traveling Tournament Problem. We prove that the 2n-team BTTP is NP-complete, but for small values of n, a distance-optimal inter-league schedule can be generated from an algorithm based on minimum-weight 4-cycle-covers. We apply our theoretical results to the 12-team Nippon Professional Baseball (NPB) league in Japan, producing a provably-optimal schedule requiring 42950 kilometres of total team travel, a 16% reduction compared to the actual distance traveled by these teams during the 2010 NPB season. We also develop a nearly-optimal inter-league tournament for the 30-team NBA league, just 3.8% higher than the trivial theoretical lower bound.
多くのプロスポーツリーグでは、対戦リーグ/カンファレンスのチームがリーグ間試合で互いに競い合います。これは二部トーナメントの一例です。本稿では、離散最適化の観点からリーグ間スケジュールを解析することにより、二部トーナメントの総移動距離を短縮する問題について考察します。この研究は、特にNBA（全米バスケットボール協会）などのリーグでは、チームが全試合をプレーするために北米を長距離移動しなければならず、多くの時間、費用、温室効果ガス排出を消費するため、スポーツのスケジュールに自然に応用できます。本研究では、よく研究されている移動トーナメント問題のリーグ間版である二部移動トーナメント問題（BTTP）を紹介します。2nチームのBTTPはNP完全ですが、nの値が小さい場合、最小重みの4サイクルカバーに基づくアルゴリズムから距離が最適なリーグ間スケジュールを生成できることが証明されています。我々は理論的結果を日本の12球団からなる日本プロ野球（NPB）リーグに適用し、チームの総移動距離が42,950キロメートルである、証明可能な最適スケジュールを作成した。これは、2010年のNPBシーズン中にこれらのチームが実際に移動した距離と比較して16%の削減となります。また、30球団からなるNBAリーグのほぼ最適なインターリーグトーナメントも開発し、自明な理論的下限よりわずか3.8%高いだけです。
Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent
複数ロボットによる敵対的パトロール：完全知識を持つ敵との対峙
The problem of adversarial multi-robot patrol has gained interest in recent years, mainly due to its immediate relevance to various security applications. In this problem, robots are required to repeatedly visit a target area in a way that maximizes their chances of detecting an adversary trying to penetrate through the patrol path. When facing a strong adversary that knows the patrol strategy of the robots, if the robots use a deterministic patrol algorithm, then in many cases it is easy for the adversary to penetrate undetected (in fact, in some of those cases the adversary can guarantee penetration). Therefore this paper presents a non-deterministic patrol framework for the robots. Assuming that the strong adversary will take advantage of its knowledge and try to penetrate through the patrol’s weakest spot, hence an optimal algorithm is one that maximizes the chances of detection in that point. We therefore present a polynomial-time algorithm for determining an optimal patrol under the Markovian strategy assumption for the robots, such that the probability of detecting the adversary in the patrol’s weakest spot is maximized. We build upon this framework and describe an optimal patrol strategy for several robotic models based on their movement abilities (directed or undirected) and sensing abilities (perfect or imperfect), and in different environment models – either patrol around a perimeter (closed polygon) or an open fence (open polyline).
敵対的マルチロボットパトロールの問題は、主にさまざまなセキュリティアプリケーションに直接関連することから、近年注目を集めています。この問題では、ロボットは、パトロール経路を突破しようとする敵対者を検出する可能性を最大化する方法を使用して、ターゲットエリアを繰り返し訪問する必要があります。ロボットの巡回戦略を知っている強力な敵に直面した場合、ロボットが決定論的な巡回アルゴリズムを使用すると、多くの場合、敵は検知されずに侵入することが容易になります（実際、そのようなケースのいくつかでは、敵は侵入を保証できます）。したがって、本論文では、ロボットのための非決定論的な巡回フレームワークを提示します。強力な敵は、その知識を利用して巡回隊の最も弱い場所を突破しようとすると仮定すると、最適なアルゴリズムはその時点での検知の可能性を最大化するアルゴリズムです。したがって、巡回隊の最も弱い場所で敵を検知する確率が最大化されるように、ロボットのマルコフ戦略仮定の下で最適な巡回隊を決定する多項式時間アルゴリズムを提示します。私たちはこのフレームワークを基に、移動能力(有向または無向)と感知能力(完全または不完全)、および周囲(閉じた多角形)または開いたフェンス(開いたポリライン)の周囲を巡回するさまざまな環境モデルに基づいて、いくつかのロボット モデルの最適な巡回戦略について説明します。
Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs
Dr.Fill：クロスワードパズルと単一重みCSPの実装されたソルバー
We describe Dr.Fill, a program that solves American-style crossword puzzles. From a technical perspective, Dr.Fill works by converting crosswords to weighted CSPs, and then using a variety of novel techniques to find a solution. These techniques include generally applicable heuristics for variable and value selection, a variant of limited discrepancy search, and postprocessing and partitioning ideas. Branch and bound is not used, as it was incompatible with postprocessing and was determined experimentally to be of little practical value. Dr.Filll’s performance on crosswords from the American Crossword Puzzle Tournament suggests that it ranks among the top fifty or so crossword solvers in the world.
アメリカ式のクロスワード パズルを解くプログラムであるDr.Fillについて説明します。技術的な観点から見ると、Dr.Fillはクロスワードパズルを重み付きCSPに変換し、さまざまな斬新な手法を用いて解を求めます。これらの手法には、変数と値の選択に関する一般的なヒューリスティック、限定矛盾検索のバリエーション、後処理と分割のアイデアなどが含まれます。分岐限定法は後処理と互換性がなく、実験的に実用的価値がほとんどないと判断されたため、使用されていません。Dr.Filllのアメリカクロスワードパズル大会でのクロスワードパズルの成績は、世界でも上位50程度のクロスワードパズル解答機にランクされていることを示しています。
Stochastic Enforced Hill-Climbing
確率的強制ヒルクライミング
Enforced hill-climbing is an effective deterministic hill-climbing technique that deals with local optima using breadth-first search (a process called “basin flooding”). We propose and evaluate a stochastic generalizationof enforced hill-climbing for online use in goal-oriented probabilistic planning problems. We assume a provided heuristic function estimating expected cost to the goal with flaws such as local optima and plateaus that thwart straightforward greedy action choice. While breadth-first search is effective in exploring basins around local optima in deterministic problems, for stochastic problems we dynamically build and solve a heuristic-based Markov decision process (MDP) model of the basin in order to find a good escape policy exiting the local optimum. We note that building this model involves integrating the heuristic into the MDP problem because the local goal is to improve the heuristic.We evaluate our proposal in twenty-four recent probabilistic planning-competition benchmark domains and twelve probabilistically interesting problems from recent literature. For evaluation, we show that stochastic enforced hill-climbing (SEH) produces better policies than greedy heuristic following for value/cost functions derived in two very different ways: one type derived by using deterministic heuristics on a deterministic relaxation and a second type derived by automatic learning of Bellman-error features from domain-specific experience. Using the first type of heuristic, SEH is shown to generally outperform all planners from the first three international probabilistic planning competitions.
強制ヒルクライミングは、幅優先探索（「ベイスンフラッディング」と呼ばれるプロセス）を用いて局所最適解を扱う、効果的な決定論的ヒルクライミング手法です。本稿では、目標指向確率計画問題におけるオンライン利用を目的とした強制ヒルクライミングの確率的一般化を提案し、評価します。目標到達までの期待コストを推定するヒューリスティック関数が、局所最適解やプラトーといった欠陥を伴い、単純な貪欲な行動選択を阻害すると仮定します。幅優先探索は決定論的問題における局所最適解周辺のベイスン探索に有効であるが、確率論的問題においては、局所最適解から抜け出すための適切な脱出方策を見つけるために、ベイスンのヒューリスティックに基づくマルコフ決定過程（MDP）モデルを動的に構築・解く。このモデルの構築には、ヒューリスティックをMDP問題に統合することが含まれることに注意してください。これは、ローカルな目標がヒューリスティックを改善することであるためです。私たちは、最近の確率的計画コンペティションのベンチマーク ドメイン24個と、最近の文献からの確率的に興味深い問題12個で提案を評価します。評価では、2つの非常に異なる方法で導出された価値/コスト関数に対して、確率的強制ヒルクライミング(SEH)が貪欲ヒューリスティックに従うよりも優れたポリシーを生成することを示します。1つは、決定論的緩和で決定論的ヒューリスティックを使用することによって導出されたタイプであり、もう1つは、ドメイン固有の経験からベルマン誤差特徴を自動学習することによって導出されたタイプです。最初のタイプのヒューリスティックを使用すると、SEHは、最初の3つの国際的な確率的計画コンペティションのすべてのプランナーよりも一般的に優れていることが示されています。
Theoretical and Practical Foundations of Large-Scale Agent-Based Micro-Storage in the Smart Grid
スマートグリッドにおける大規模エージェントベースマイクロストレージの理論的および実践的基盤
In this paper, we present a novel decentralised management technique that allows electricity micro-storage devices, deployed within individual homes as part of a smart electricity grid, to converge to profitable and efficient behaviours. Specifically, we propose the use of software agents, residing on the users’ smart meters, to automate and optimise the charging cycle of micro-storage devices in the home to minimise its costs, and we present a study of both the theoretical underpinnings and the implications of a practical solution, of using software agents for such micro-storage management. First, by formalising the strategic choice each agent makes in deciding when to charge its battery, we develop a game-theoretic framework within which we can analyse the competitive equilibria of an electricity grid populated by such agents and hence predict the best consumption profile for that population given their battery properties and individual load profiles. Our framework also allows us to compute theoretical bounds on the amount of storage that will be adopted by the population. Second, to analyse the practical implications of micro-storage deployments in the grid, we present a novel algorithm that each agent can use to optimise its battery storage profile in order to minimise its owner’s costs. This algorithm uses a learning strategy that allows it to adapt as the price of electricity changes in real-time, and we show that the adoption of these strategies results in the system converging to the theoretical equilibria. Finally, we empirically evaluate the adoption of our micro-storage management technique within a complex setting, based on the UK electricity market, where agents may have widely varying load profiles, battery types, and learning rates. In this case, our approach yields savings of up to 14% in energy cost for an average consumer using a storage device with a capacity of less than 4.5 kWh and up to a 7% reduction in carbon emissions resulting from electricity generation (with only domestic consumers adopting micro-storage and, commercial and industrial consumers not changing their demand). Moreover, corroborating our theoretical bound, an equilibrium is shown to exist where no more than 48% of households would wish to own storage devices and where social welfare would also be improved (yielding overall annual savings of nearly £1.5B).
本稿では、スマート電力網の一部として各家庭に設置された電力マイクロストレージデバイスが、収益性と効率性を兼ね備えた動作に収束することを可能にする、新たな分散管理手法を提示します。具体的には、ユーザーのスマートメーターに常駐するソフトウェアエージェントを用いて、家庭内のマイクロストレージデバイスの充電サイクルを自動化・最適化し、コストを最小化することを提案します。また、このようなマイクロストレージ管理にソフトウェアエージェントを用いるという、理論的根拠と実用的なソリューションの含意の両方について検討します。まず、各エージェントがバッテリーの充電時期を決定する際に行う戦略的選択を形式化することにより、ゲーム理論的枠組みを開発します。この枠組みの中で、このようなエージェントで構成される電力網の競争均衡を分析し、バッテリー特性と個々の負荷プロファイルに基づいて、その集団にとって最適な消費プロファイルを予測することができます。我々のフレームワークは、人口が導入するであろうストレージ容量の理論的な限界を計算することも可能にします。次に、電力網におけるマイクロストレージ導入の実際的な影響を分析するために、各エージェントがバッテリーストレージプロファイルを最適化し、所有者のコストを最小化するために使用できる新しいアルゴリズムを提示します。このアルゴリズムは、電力価格のリアルタイム変動に適応できる学習戦略を採用しており、これらの戦略を採用することで、システムが理論的な均衡に収束することを示します。最後に、英国の電力市場をベースとした複雑な設定において、我々のマイクロストレージ管理手法の導入効果を実証的に評価します。この設定では、エージェントの負荷プロファイル、バッテリーの種類、学習率が大きく異なる場合があります。この場合、我々のアプローチは、4.5 kWh未満の容量のストレージデバイスを使用する平均的な消費者のエネルギーコストを最大14%削減し、発電による炭素排出量を最大7%削減します（家庭用消費者のみがマイクロストレージを導入し、商業および産業用消費者は需要が変化しない場合）。さらに、私たちの理論的な限界を裏付けるように、ストレージデバイスを所有したい世帯が48%以下で、社会福祉も向上する(年間全体で約15億ポンドの節約になる)均衡が存在することが示されています。
Defeasible Inclusions in Low-Complexity DLs
低複雑度DLにおける破棄可能な包含
Some of the applications of OWL and RDF (e.g. biomedical knowledge representation and semantic policy formulation) call for extensions of these languages with nonmonotonic constructs such as inheritance with overriding. Nonmonotonic description logics have been studied for many years, however no practical such knowledge representation languages exist, due to a combination of semantic difficulties and high computational complexity. Independently, low-complexity description logics such as DL-lite and EL have been introduced and incorporated in the OWL standard. Therefore, it is interesting to see whether the syntactic restrictions characterizing DL-lite and EL bring computational benefits to their nonmonotonic versions, too. In this paper we extensively investigate the computational complexity of Circumscription when knowledge bases are formulated in DL-lite_R, EL, and fragments thereof. We identify fragments whose complexity ranges from P to the second level of the polynomial hierarchy, as well as fragments whose complexity raises to PSPACE and beyond.
OWLとRDFのアプリケーション（例えば、生物医学的知識表現や意味的ポリシー策定）の中には、オーバーライドを伴う継承などの非単調な構成要素を備えたこれらの言語の拡張を必要とするものがあります。非単調な記述論理は長年研究されてきましたが、意味的な難しさと高い計算複雑性の組み合わせにより、実用的な知識表現言語は存在しません。それとは別に、DL-liteやELといった低複雑性の記述論理が導入され、OWL標準に組み込まれています。したがって、DL-liteとELを特徴付ける構文上の制約が、それらの非単調なバージョンにも計算上の利点をもたらすかどうかを見ることは興味深いことです。本稿では、知識ベースがDL-lite_R、EL、およびそれらの断片で定式化されている場合のCircumscriptionの計算複雑性を徹底的に調査します。我々は、複雑度がPから多項式階層の第2レベルまでの範囲にあるフラグメントと、複雑度がPSPACE以上に上昇するフラグメントを特定します。
Combining Evaluation Metrics via the Unanimous Improvement Ratio and its Application to Clustering Tasks
全会一致改善率による評価指標の統合とクラスタリングタスクへの応用
Many Artificial Intelligence tasks cannot be evaluated with a single quality criterion and some sort of weighted combination is needed to provide system rankings. A problem of weighted combination measures is that slight changes in the relative weights may produce substantial changes in the system rankings. This paper introduces the Unanimous Improvement Ratio (UIR), a measure that complements standard metric combination criteria (such as van Rijsbergens F-measure) and indicates how robust the measured differences are to changes in the relative weights of the individual metrics. UIR is meant to elucidate whether a perceived difference between two systems is an artifact of how individual metrics are weighted.Besides discussing the theoretical foundations of UIR, this paper presents empirical results that confirm the validity and usefulness of the metric for the Text Clustering problem, where there is a tradeoff between precision and recall based metrics and results are particularly sensitive to the weighting scheme used to combine them. Remarkably, our experiments show that UIR can be used as a predictor of how well differences between systems measured on a given test bed will also hold in a different test bed.
多くの人工知能タスクは、単一の品質基準では評価できず、システムのランキングを提供するには何らかの重み付けされた組み合わせが必要です。重み付けされた組み合わせの尺度の問題は、相対的な重みのわずかな変化がシステムのランキングに大きな変化をもたらす可能性があることです。この論文では、標準的なメトリックの組み合わせ基準(van Rijsbergens F尺度など)を補完し、測定された差異が個々のメトリックの相対的な重みの変化に対してどれだけ堅牢であるかを示す尺度である、全員一致の改善率(UIR)を紹介します。UIRは、2つのシステム間で認識される差異が、個々のメトリックの重み付け方法によるアーティファクトであるかどうかを明らかにすることを目的としています。UIRの理論的基礎について説明するほかに、この論文では、精度と再現率に基づくメトリックの間にトレードオフがあり、結果がそれらを組み合わせるために使用される重み付けスキームに特に敏感であるテキスト クラスタリングの問題に対するメトリックの妥当性と有用性を確認する実証的結果を示します。驚くべきことに、我々の実験は、UIRが、あるテストベッドで測定されたシステム間の差異が、異なるテストベッドでもどの程度当てはまるかを予測する指標として使用できることを示しています。
Finding Consensus Bayesian Network Structures
コンセンサスベイジアンネットワークの発見構造
Suppose that multiple experts (or learning algorithms) provide us with alternative Bayesian network (BN) structures over a domain, and that we are interested in combining them into a single consensus BN structure. Specifically, we are interested in that the consensus BN structure only represents independences all the given BN structures agree upon and that it has as few parameters associated as possible. In this paper, we prove that there may exist several non-equivalent consensus BN structures and that finding one of them is NP-hard. Thus, we decide to resort to heuristics to find an approximated consensus BN structure. In this paper, we consider the heuristic proposed by Matzkevich and Abramson, which builds upon two algorithms, called Methods A and B, for efficiently deriving the minimal directed independence map of a BN structure relative to a given node ordering. Methods A and B are claimed to be correct although no proof is provided (a proof is just sketched). In this paper, we show that Methods A and B are not correct and propose a correction of them.
複数のエキスパート（または学習アルゴリズム）が、あるドメインにおいて複数のベイジアンネットワーク（BN）構造を提供し、それらを単一のコンセンサスBN構造に統合することに関心があるとします。具体的には、コンセンサスBN構造は、与えられたBN構造すべてが同意する独立性のみを表現し、関連するパラメータが可能な限り少ないことに注目します。本稿では、等価でないコンセンサスBN構造が複数存在する可能性があり、そのうちの1つを見つけることがNP困難であることを証明します。そこで、近似的なコンセンサスBN構造を見つけるために、ヒューリスティックスを用いることにしました。本論文では、MatzkevichとAbramsonによって提案されたヒューリスティックについて考察します。このヒューリスティックは、与えられたノード順序に対するBN構造の最小有向独立写像を効率的に導くための、方法Aと方法Bと呼ばれる2つのアルゴリズムに基づく。方法Aと方法Bは正しいと主張されているが、証明は示されていない（証明は概略のみ）。本論文では、方法Aと方法Bが正しくないことを示し、それらの修正を提案します。
Drake: An Efficient Executive for Temporal Plans with Choice
Drake：選択を伴う時間的計画のための効率的な実行装置
This work presents Drake, a dynamic executive for temporal plans with choice. Dynamic plan execution strategies allow an autonomous agent to react quickly to unfolding events, improving the robustness of the agent. Prior work developed methods for dynamically dispatching Simple Temporal Networks, and further research enriched the expressiveness of the plans executives could handle, including discrete choices, which are the focus of this work. However, in some approaches to date, these additional choices induce significant storage or latency requirements to make flexible execution possible. Drake is designed to leverage the low latency made possible by a preprocessing step called compilation, while avoiding high memory costs through a compact representation. We leverage the concepts of labels and environments, taken from prior work in Assumption-based Truth Maintenance Systems (ATMS), to concisely record the implications of the discrete choices, exploiting the structure of the plan to avoid redundant reasoning or storage. Our labeling and maintenance scheme, called the Labeled Value Set Maintenance System, is distinguished by its focus on properties fundamental to temporal problems, and, more generally, weighted graph algorithms. In particular, the maintenance system focuses on maintaining a minimal representation of non-dominated constraints. We benchmark Drake’s performance on random structured problems, and find that Drake reduces the size of the compiled representation by a factor of over 500 for large problems, while incurring only a modest increase in run-time latency, compared to prior work in compiled executives for temporal plans with discrete choices.
この研究では、選択を伴う時間的プランの動的実行装置であるDrakeを紹介します。動的計画実行戦略は、自律エージェントが展開するイベントに迅速に対応することを可能にし、エージェントの堅牢性を向上させます。先行研究では、Simple Temporal Networksを動的にディスパッチする手法が開発され、さらなる研究によって、本研究の焦点である離散的選択を含む、実行側が処理できる計画の表現力が強化されました。しかしながら、これまでのいくつかのアプローチでは、これらの追加的な選択によって、柔軟な実行を可能にするために、大きなストレージまたはレイテンシ要件が発生します。Drakeは、コンパイルと呼ばれる前処理ステップによって実現される低レイテンシを活用しながら、コンパクトな表現によって高いメモリコストを回避するように設計されています。我々は、仮定に基づく真理維持システム（ATMS）における先行研究から取り入れたラベルと環境の概念を活用し、離散的選択の含意を簡潔に記録し、計画の構造を利用して冗長な推論やストレージを回避します。ラベル付き値セット維持システムと呼ばれる我々のラベル付けおよび維持スキームは、時間的問題、そしてより一般的には重み付きグラフアルゴリズムの基本的な特性に焦点を当てている点で際立っています。特に、メンテナンスシステムは、非劣制約の最小限の表現を維持することに重点を置いています。ランダム構造化問題におけるDrakeのパフォーマンスをベンチマークした結果、Drakeは大規模な問題においてコンパイル済み表現のサイズを500分の1以上削減し、離散選択を伴う時相プランのコンパイル済み実行システムにおける先行研究と比較して、実行時のレイテンシはわずかにしか増加しないことがわかりました。
Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling
サンプリングを用いた近似ナッシュ均衡とロバストな最良応答の計算
This article discusses two contributions to decision-making in complex partially observable stochastic games. First, we apply two state-of-the-art search techniques that use Monte-Carlo sampling to the task of approximating a Nash-Equilibrium (NE) in such games, namely Monte-Carlo Tree Search (MCTS) and Monte-Carlo Counterfactual Regret Minimization (MCCFR). MCTS has been proven to approximate a NE in perfect-information games. We show that the algorithm quickly finds a reasonably strong strategy (but not a NE) in a complex imperfect information game, i.e. Poker. MCCFR on the other hand has theoretical NE convergence guarantees in such a game. We apply MCCFR for the first time in Poker. Based on our experiments, we may conclude that MCTS is a valid approach if one wants to learn reasonably strong strategies fast, whereas MCCFR is the better choice if the quality of the strategy is most important. Our second contribution relates to the observation that a NE is not a best response against players that are not playing a NE. We present Monte-Carlo Restricted Nash Response (MCRNR), a sample-based algorithm for the computation of restricted Nash strategies. These are robust best-response strategies that (1) exploit non-NE opponents more than playing a NE and (2) are not (overly) exploitable by other strategies. We combine the advantages of two state-of-the-art algorithms, i.e. MCCFR and Restricted Nash Response (RNR). MCRNR samples only relevant parts of the game tree. We show that MCRNR learns quicker than standard RNR in smaller games. Also we show in Poker that MCRNR learns robust best-response strategies fast, and that these strategies exploit opponents more than playing a NE does.
本稿では、複雑で部分的に観測可能な確率ゲームにおける意思決定への2つの貢献について論じる。まず、モンテ カルロ サンプリングを用いた最先端の2つの探索手法、すなわちモンテ カルロ木探索(MCTS)とモンテ カルロ反事実的リグレット最小化(MCCFR)を、このようなゲームでナッシュ均衡(NE)を近似するタスクに適用します。MCTSは、完全情報ゲームでNEを近似することが証明されています。このアルゴリズムにより、複雑な不完全情報ゲーム、つまりポーカーで、適度に強い戦略(ただしNEではない)が迅速に見つかることを示す。一方、MCCFRは、このようなゲームで理論的にNE収束保証を持つ。我々は、ポーカーに初めてMCCFRを適用します。実験に基づいて、適度に強い戦略を迅速に学習したい場合はMCTSが有効なアプローチであるが、戦略の質が最も重要である場合はMCCFRの方が優れた選択であると結論付けることができます。2つ目の貢献は、NEをプレイしていないプレイヤーに対しては、NEは最善の対応ではないという観察に関係しています。制限付きナッシュ戦略を計算するためのサンプルベースアルゴリズムであるモンテカルロ制限付きナッシュ応答（MCRNR）を紹介します。これらは、（1）NEをプレイするよりも非NE対戦相手をより多く利用し、（2）他の戦略によって（過度に）利用されない、堅牢な最善の対応戦略です。私たちは、2つの最先端アルゴリズム、すなわちMCCFRと制限付きナッシュ応答（RNR）の利点を組み合わせます。MCRNRはゲームツリーの関連部分のみをサンプリングします。小規模ゲームでは、MCRNRが標準のRNRよりも速く学習することを示します。また、ポーカーにおいて、MCRNRが堅牢な最善の対応戦略を速く学習し、これらの戦略がNEをプレイするよりも対戦相手をより多く利用することを示しました。
MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees
MAPP：扱いやすさと完全性を保証するスケーラブルなマルチエージェント経路計画アルゴリズム
Multi-agent path planning is a challenging problem with numerous real-life applications. Running a centralized search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the state space size is exponential in the number of mobile units. Traditional decentralized approaches, such as FAR and WHCA*, are faster and more scalable, being based on problem decomposition. However, such methods are incomplete and provide no guarantees with respect to the running time or the solution quality. They are not necessarily able to tell in a reasonable time whether they would succeed in finding a solution to a given instance. We introduce MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. We present a basic version and several extensions.They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Even though all algorithmic versions are incomplete in the general case, each provides formal guarantees on problems it can solve. For each version, we discuss the algorithm’s completeness with respect to clearly defined subclasses of instances.Experiments were run on realistic game grid maps. MAPP solved 99.86% of all mobile units, which is 18–22% better than the percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably solvable during the first stage of plan computation. Parts of MAPP’s computation can be re-used across instances on the same map. Speed-wise, MAPP is competitive or significantly faster than WHCA*, depending on whether MAPP performs all computations from scratch. When data that MAPP can re-use are preprocessed offline and readily available, MAPP is slower than the very fast FAR algorithm by a factor of 2.18 on average. MAPP’s solutions are on average 20% longer than FAR’s solutions and 7–31% longer than WHCA*’s solutions.
マルチエージェント経路計画は、多くの実世界で応用されている難解な問題です。A*のような集中探索を全ユニットの結合状態空間で実行することは、完全かつコスト最適化を実現しますが、状態空間のサイズが移動ユニット数に対して指数関数的に大きくなるため、スケーラビリティは低くなります。FARやWHCA*といった従来の分散型アプローチは、問題の分解に基づいているため、より高速でスケーラブルです。しかし、これらの手法は不完全であり、実行時間や解の品質に関して保証を提供しません。これらの手法は、与えられたインスタンスに対する解の発見に成功するかどうかを、必ずしも妥当な時間内に判断できるとは限りません。本稿では、無向グラフ上のマルチエージェント経路計画のための扱いやすいアルゴリズムであるMAPPを紹介します。基本バージョンといくつかの拡張バージョンを紹介します。これらのアルゴリズムは、実行時間、メモリ要件、および解の長さについて、低多項式の最悪ケース上限を持ちます。すべてのアルゴリズムバージョンは一般的なケースでは不完全ですが、それぞれが解決可能な問題に対して形式的な保証を提供します。各バージョンについて、明確に定義されたインスタンスのサブクラスに関するアルゴリズムの完全性について説明します。実験は、リアルなゲーム グリッド マップで実行されました。MAPPはすべての移動ユニットの99.86%を解決しました。これは、FARとWHCA*の割合よりも18～22%優れています。MAPPは、プラン計算の最初の段階で、すべてのユニットの98.82%を証明可能に解決可能としてマークしました。MAPPの計算の一部は、同じマップ上のインスタンス間で再利用できます。速度の点では、MAPPがすべての計算を最初から実行するかどうかに応じて、WHCA*と競合するか、大幅に高速です。MAPPが再利用できるデータがオフラインで前処理され、すぐに使用できる場合、MAPPは非常に高速なFARアルゴリズムよりも平均で2.18倍遅くなります。MAPPのソリューションは、平均してFARのソリューションよりも20%長く、WHCA*のソリューションよりも7～31%長くなります。
Cloning in Elections: Finding the Possible Winners
選挙におけるクローニング：可能性のある勝者の発見
We consider the problem of manipulating elections by cloning candidates. In our model, a manipulator can replace each candidate c by several clones, i.e., new candidates that are so similar to c that each voter simply replaces c in his vote with a block of these new candidates, ranked consecutively. The outcome of the resulting election may then depend on the number of clones as well as on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of common voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with two related problems: the problem of control by adding candidates and the problem of possible (co)winners when new alternatives can join.
候補者のクローン作成による選挙操作の問題を考察します。本モデルでは、操作者は各候補者cを複数のクローン、すなわちcに非常に類似した新しい候補者に置き換えることができます。これらの新しい候補者はcに非常に類似しているため、各投票者は自分の投票において、これらの新しい候補者のブロックを順番に並べた形でcに置き換えるだけでよい。その結果生じる選挙の結果は、クローンの数だけでなく、各投票者がブロック内でクローンをどのように並べるかによっても左右されます。クローン作成操作が成功することの意味を定式化し（これは驚くほど繊細な問題であることが判明する）、いくつかの一般的な投票規則について、クローン作成操作が成功する場合の選好プロファイルを特徴付ける。また、各クローンの作成にコストがかかるモデルを考察し、最小コストのクローン作成操作を見つける複雑さを検証します。最後に、クローン作成を、候補者の追加による制御の問題と、新たな選択肢が加わった場合の（共）勝者の可能性の問題という2つの関連問題と比較します。
Unfounded Sets and Well-Founded Semantics of Answer Set Programs with Aggregates
集約を含む解集合プログラムの非根拠集合と妥当な意味論
Logic programs with aggregates (LPA) are one of the major linguistic extensions to Logic Programming (LP). In this work, we propose a generalization of the notions of unfounded set and well-founded semantics for programs with monotone and antimonotone aggregates (LPAma programs). In particular, we present a new notion of unfounded set for LPAma programs, which is a sound generalization of the original definition for standard (aggregate-free) LP. On this basis, we define a well-founded operator for LPAma programs, the fixpoint of which is called well-founded model (or well-founded semantics) for LPAma programs. The most important properties of unfounded sets and the well-founded semantics for standard LP are retained by this generalization, notably existence and uniqueness of the well-founded model, together with a strong relationship to the answer set semantics for LPAma programs. We show that one of the D-well-founded semantics, defined by Pelov, Denecker, and Bruynooghe for a broader class of aggregates using approximating operators, coincides with the well-founded model as defined in this work on LPAma programs. We also discuss some complexity issues, most importantly we give a formal proof of tractable computation of the well-founded model for LPA programs. Moreover, we prove that for general LPA programs, which may contain aggregates that are neither monotone nor antimonotone, deciding satisfaction of aggregate expressions with respect to partial interpretations is coNP-complete. As a consequence, a well-founded semantics for general LPA programs that allows for tractable computation is unlikely to exist, which justifies the restriction on LPAma programs. Finally, we present a prototype system extending DLV, which supports the well-founded semantics for LPAma programs, at the time of writing the only implemented system that does so. Experiments with this prototype show significant computational advantages of aggregate constructs over equivalent aggregate-free encodings.
集積体を含む論理プログラム(LPA)は、論理プログラミング(LP)の主要な言語拡張の1つです。本研究では、単調および反単調な集積体を含むプログラム(LPAmaプログラム)に対する非基礎集合とwell-founded意味論の概念の一般化を提案します。特に、LPAmaプログラムに対する非基礎集合という新しい概念を提示します。これは、標準(集積体なし) LPの元の定義を適切に一般化したものです。これに基づいて、LPAmaプログラムのwell-founded演算子を定義します。この演算子の不動点は、LPAmaプログラムのwell-foundedモデル(またはwell-founded意味論)と呼ばれます。非基礎集合と標準LPのwell-founded意味論の最も重要な特性、特にwell-foundedモデルの存在と一意性、およびLPAmaプログラムの解答集合意味論との強い関係は、この一般化によって保持されます。Pelov、Denecker、Bruynoogheによって近似演算子を用いたより広いクラスの集合体に対して定義されたD-well-founded意味論の一つが、本研究でLPAmaプログラムに関して定義したwell-foundedモデルと一致することを示す。また、いくつかの計算量問題についても議論します。最も重要な点として、LPAプログラムに対するwell-foundedモデルの計算可能の形式的証明を与える。さらに、単調でも反単調でもない集合体を含む可能性のある一般的なLPAプログラムにおいて、部分解釈に関する集合体の式の充足判定はcoNP完全であることを証明した。結果として、一般的なLPAプログラムに対して計算可能となるwell-founded意味論は存在しそうになく、LPAmaプログラムに対する制約が正当化されます。最後に、DLVを拡張したプロトタイプシステムを提示します。このシステムはLPAmaプログラムのwell-founded意味論をサポートするもので、執筆時点ではこれが唯一の実装システムです。このプロトタイプを用いた実験により、集合体構造は、同等の集合体を含まない符号化法に比べて計算上の大きな利点を持つことが明らかになった。
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
適応的劣モジュラリティ：能動学習と確率的最適化における理論と応用
Many problems in artificial intelligence require adaptively making a sequence of decisions with uncertain outcomes under partial observability. Solving such stochastic optimization problems is a fundamental but notoriously difficult challenge. In this paper, we introduce the concept of adaptive submodularity, generalizing submodular set functions to adaptive policies. We prove that if a problem satisfies this property, a simple adaptive greedy algorithm is guaranteed to be competitive with the optimal policy. In addition to providing performance guarantees for both stochastic maximization and coverage, adaptive submodularity can be exploited to drastically speed up the greedy algorithm by using lazy evaluations. We illustrate the usefulness of the concept by giving several examples of adaptive submodular objectives arising in diverse AI applications including management of sensing resources, viral marketing and active learning. Proving adaptive submodularity for these problems allows us to recover existing results in these applications as special cases, improve approximation guarantees and handle natural generalizations.
人工知能における多くの問題は、部分観測性の下で不確実な結果を伴う一連の意思決定を適応的に行うことを要求します。このような確率的最適化問題を解くことは、基礎的でありながらも非常に困難な課題です。本稿では、適応的劣モジュラ性の概念を導入し、劣モジュラ集合関数を適応的方策に一般化します。問題がこの性質を満たす場合、単純な適応的貪欲アルゴリズムが最適方策と競合することが保証されることを証明します。適応的劣モジュラ性は、確率的最大化と被覆率の両方の性能保証を提供するだけでなく、遅延評価を用いることで貪欲アルゴリズムを大幅に高速化するために活用できます。本稿では、センシングリソース管理、バイラルマーケティング、能動学習など、多様なAIアプリケーションで生じる適応的劣モジュラ目的関数の例をいくつか挙げ、この概念の有用性を示す。これらの問題に対する適応的劣モジュラ性を証明することで、これらのアプリケーションにおける既存の結果を特殊なケースとして復元し、近似保証を向上させ、自然な一般化を扱うことができるようになります。
Making Decisions Using Sets of Probabilities: Updating, Time Consistency, and Calibration
確率集合を用いた意思決定：更新、時間一貫性、キャリブレーション
We consider how an agent should update her beliefs when her beliefs are represented by a set P of probability distributions, given that the agent makes decisions using the minimax criterion, perhaps the best-studied and most commonly-used criterion in the literature. We adopt a game-theoretic framework, where the agent plays against a bookie, who chooses some distribution from P. We consider two reasonable games that differ in what the bookie knows when he makes his choice. Anomalies that have been observed before, like time inconsistency, can be understood as arising because different games are being played, against bookies with different information. We characterize the important special cases in which the optimal decision rules according to the minimax criterion amount to either conditioning or simply ignoring the information. Finally, we consider the relationship between updating and calibration when uncertainty is described by sets of probabilities. Our results emphasize the key role of the rectangularity condition of Epstein and Schneider.
エージェントがミニマックス基準（おそらく文献で最も研究され、最も一般的に使用されている基準）を用いて意思決定を行う場合、エージェントの信念が確率分布の集合Pで表されるときに、エージェントがどのように信念を更新すべきかを考察します。エージェントは、Pから何らかの分布を選択するブックメーカーと対戦するゲーム理論的枠組みを採用します。ブックメーカーが選択を行う際に知っている情報が異なる、2つの合理的なゲームを考察します。時間の不整合など、これまで観察されてきた異常現象は、異なる情報を持つブックメーカーに対して、異なる試合が行われていることから生じると理解できます。ミニマックス基準に基づく最適な意思決定ルールが、情報の条件付け、あるいは単に情報の無視のいずれかに帰着する重要な特殊なケースを特徴付ける。最後に、不確実性が確率集合で記述される場合の更新と較正の関係を考察します。我々の結果は、エプスタインとシュナイダーの長方形条件の重要な役割を強調します。
Learning to Make Predictions In Partially Observable Environments Without a Generative Model
生成モデルを用いない部分観測環境における予測学習
When faced with the problem of learning a model of a high-dimensional environment, a common approach is to limit the model to make only a restricted set of predictions, thereby simplifying the learning problem. These partial models may be directly useful for making decisions or may be combined together to form a more complete, structured model. However, in partially observable (non-Markov) environments, standard model-learning methods learn generative models, i.e. models that provide a probability distribution over all possible futures (such as POMDPs). It is not straightforward to restrict such models to make only certain predictions, and doing so does not always simplify the learning problem. In this paper we present prediction profile models: non-generative partial models for partially observable systems that make only a given set of predictions, and are therefore far simpler than generative models in some cases. We formalize the problem of learning a prediction profile model as a transformation of the original model-learning problem, and show empirically that one can learn prediction profile models that make a small set of important predictions even in systems that are too complex for standard generative models.
高次元環境のモデルを学習するという問題に直面した場合、一般的なアプローチは、モデルを限定された予測集合のみに制限し、学習問題を単純化することにあります。これらの部分モデルは、意思決定に直接役立つ場合もあれば、より完全で構造化されたモデルを形成するために組み合わせる場合もあります。しかし、部分的に観測可能な（非マルコフ）環境では、標準的なモデル学習手法は生成モデル、すなわちすべての可能性のある未来（POMDPなど）にわたる確率分布を提供するモデルを学習します。このようなモデルを特定の予測のみに限定することは容易ではなく、また、そうすることで学習問題が必ずしも単純化されるわけでもありません。本稿では、予測プロファイルモデルを提示します。これは、部分観測システムのための非生成的部分モデルであり、与えられた予測セットのみを行うため、場合によっては生成モデルよりもはるかに単純です。予測プロファイルモデルの学習問題を、元のモデル学習問題の変形として定式化し、標準的な生成モデルでは複雑すぎるシステムであっても、重要な予測の少数の集合を行う予測プロファイルモデルを学習できることを実証的に示します。
On the Link between Partial Meet, Kernel, and Infra Contraction and its Application to Horn Logic
部分ミート、カーネル、インフラ縮約の関連性とホーン論理への応用について
Standard belief change assumes an underlying logic containing full classical propositional logic. However, there are good reasons for considering belief change in less expressive logics as well. In this paper we build on recent investigations by Delgrande on contraction for Horn logic. We show that the standard basic form of contraction, partial meet, is too strong in the Horn case. This result stands in contrast to Delgrandes conjecture that orderly maxichoice is the appropriate form of contraction for Horn logic. We then define a more appropriate notion of basic contraction for the Horn case, influenced by the convexity property holding for full propositional logic and which we refer to as infra contraction. The main contribution of this work is a result which shows that the construction method for Horn contraction for belief sets based on our infra remainder sets corresponds exactly to Hanssons classical kernel contraction for belief sets, when restricted to Horn logic. This result is obtained via a detour through contraction for belief bases. We prove that kernel contraction for belief bases produces precisely the same results as the belief base version of infra contraction. The use of belief bases to obtain this result provides evidence for the conjecture that Horn belief change is best viewed as a ‘hybrid’ version of belief set change and belief base change. One of the consequences of the link with base contraction is the provision of a representation result for Horn contraction for belief sets in which a version of the Core-retainment postulate features.
標準的な信念変更は、完全な古典的命題論理を含む基礎論理を前提としています。しかし、表現力の低い論理においても信念変更を考慮する十分な理由があります。本論文では、デルグランデによるホーン論理の縮約に関する最近の研究を基にしています。縮約の標準的な基本形式である部分的ミートは、ホーン論理の場合では強すぎることを示します。この結果は、ホーン論理の縮約の適切な形式は秩序ある最大選択であるというデルグランデの予想とは対照的です。次に、完全な命題論理で成立する凸性特性の影響を受け、ホーン論理の場合のより適切な基本縮約の概念を定義し、これをインフラ縮約と呼びます。本研究の主な貢献は、インフラ剰余集合に基づく信念集合のホーン縮約の構築方法が、ホーン論理に限定した場合、ハンソンの信念集合の古典的なカーネル縮約と正確に一致することを示す結果です。この結果は、信念基底の縮約を経由することで得られます。我々は、信念基底に対するカーネル縮約が、インフラ縮約の信念基底版と全く同じ結果を生み出すことを証明します。この結果を得るために信念基底を用いることは、ホーン信念変化は信念集合変化と信念基底変化の「ハイブリッド」版として捉えるのが最適であるという仮説の証拠となります。基底縮約との関連による帰結の一つは、コア保持公準の特徴を持つ信念集合に対するホーン縮約の表現結果の提供です。
Most Relevant Explanation in Bayesian Networks
ベイジアンネットワークにおける最も関連性の高い説明
A major inference task in Bayesian networks is explaining why some variables are observed in their particular states using a set of target variables. Existing methods for solving this problem often generate explanations that are either too simple (underspecified) or too complex (overspecified). In this paper, we introduce a method called Most Relevant Explanation (MRE) which finds a partial instantiation of the target variables that maximizes the generalized Bayes factor (GBF) as the best explanation for the given evidence. Our study shows that GBF has several theoretical properties that enable MRE to automatically identify the most relevant target variables in forming its explanation. In particular, conditional Bayes factor (CBF), defined as the GBF of a new explanation conditioned on an existing explanation, provides a soft measure on the degree of relevance of the variables in the new explanation in explaining the evidence given the existing explanation. As a result, MRE is able to automatically prune less relevant variables from its explanation. We also show that CBF is able to capture well the explaining-away phenomenon that is often represented in Bayesian networks. Moreover, we define two dominance relations between the candidate solutions and use the relations to generalize MRE to find a set of top explanations that is both diverse and representative. Case studies on several benchmark diagnostic Bayesian networks show that MRE is often able to find explanatory hypotheses that are not only precise but also concise.
ベイジアンネットワークにおける主要な推論タスクは、一連のターゲット変数を用いて、いくつかの変数が特定の状態で観測される理由を説明することです。この問題を解決するための既存の手法では、多くの場合、単純すぎる（指定不足）または複雑すぎる（指定過剰）説明が生成されます。本稿では、与えられた証拠に対する最良の説明として一般化ベイズ係数（GBF）を最大化する対象変数の部分的なインスタンス化を求める、最も関連性の高い説明（MRE）と呼ばれる手法を紹介します。本研究では、GBFには、MREが説明を形成する際に最も関連性の高い対象変数を自動的に特定することを可能にするいくつかの理論的特性があることを示しています。特に、既存の説明を条件とする新しい説明のGBFとして定義される条件付きベイズ係数（CBF）は、既存の説明を前提とした証拠の説明において、新しい説明における変数の関連度合いを示すソフトな尺度を提供します。その結果、MREは関連性の低い変数を説明から自動的に除去することができます。また、CBFはベイジアンネットワークでよく見られる説明の省略現象をうまく捉えることができることも示します。さらに、候補解間の2つの優位関係を定義し、これらの関係を用いてMREを一般化し、多様性と代表性を兼ね備えた最上位の説明集合を見つけます。いくつかのベンチマーク診断ベイジアン ネットワークに関するケース スタディでは、MREが正確であるだけでなく簡潔な説明仮説を見つけられることが多いことが示されています。
Centrality-as-Relevance: Support Sets and Similarity as Geometric Proximity
関連性としての中心性：幾何学的近接性としてのサポートセットと類似性
In automatic summarization, centrality-as-relevance means that the most important content of an information source, or a collection of information sources, corresponds to the most central passages, considering a representation where such notion makes sense (graph, spatial, etc.). We assess the main paradigms, and introduce a new centrality-based relevance model for automatic summarization that relies on the use of support sets to better estimate the relevant content. Geometric proximity is used to compute semantic relatedness. Centrality (relevance) is determined by considering the whole input source (and not only local information), and by taking into account the existence of minor topics or lateral subjects in the information sources to be summarized. The method consists in creating, for each passage of the input source, a support set consisting only of the most semantically related passages. Then, the determination of the most relevant content is achieved by selecting the passages that occur in the largest number of support sets. This model produces extractive summaries that are generic, and language- and domain-independent. Thorough automatic evaluation shows that the method achieves state-of-the-art performance, both in written text, and automatically transcribed speech summarization, including when compared to considerably more complex approaches.
自動要約において、関連性としての中心性とは、情報源または情報源のコレクションの最も重要なコンテンツが、そのような概念が意味をなす表現（グラフ、空間など）を考慮した最も中心的なパッセージに対応することを意味します。主要なパラダイムを評価し、サポートセットの使用によって関連コンテンツをより適切に推定する、自動要約のための新しい中心性ベースの関連性モデルを紹介します。意味的な関連性を計算するために、幾何学的な近接性が使用されます。中心性（関連性）は、入力ソース全体（ローカル情報だけでなく）を考慮し、要約対象となる情報ソース内のマイナートピックや横断的な主題の存在を考慮することで決定されます。この手法では、入力ソースの各パッセージについて、意味的に最も関連性の高いパッセージのみで構成されるサポートセットを作成します。次に、最も多くのサポートセットに出現するパッセージを選択することで、最も関連性の高いコンテンツを決定します。このモデルは、汎用的で言語およびドメインに依存しない抽出要約を生成します。徹底的な自動評価により、この手法は、書かれたテキストと自動書き起こし音声要約の両方において、はるかに複雑なアプローチと比較しても、最先端のパフォーマンスを達成することが示されています。
Representing and Reasoning with Qualitative Preferences for Compositional Systems
構成システムの質的選好を用いた表現と推論
Many applications, e.g., Web service composition, complex system design, team formation, etc., rely on methods for identifying collections of objects or entities satisfying some functional requirement. Among the collections that satisfy the functional requirement, it is often necessary to identify one or more collections that are optimal with respect to user preferences over a set of attributes that describe the non-functional properties of the collection.We develop a formalism that lets users express the relative importance among attributes and qualitative preferences over the valuations of each attribute. We define a dominance relation that allows us to compare collections of objects in terms of preferences over attributes of the objects that make up the collection. We establish some key properties of the dominance relation. In particular, we show that the dominance relation is a strict partial order when the intra-attribute preference relations are strict partial orders and the relative importance preference relation is an interval order.We provide algorithms that use this dominance relation to identify the set of most preferred collections. We show that under certain conditions, the algorithms are guaranteed to return only (sound), all (complete), or at least one (weakly complete) of the most preferred collections. We present results of simulation experiments comparing the proposed algorithms with respect to (a) the quality of solutions (number of most preferred solutions) produced by the algorithms, and (b) their performance and efficiency. We also explore some interesting conjectures suggested by the results of our experiments that relate the properties of the user preferences, the dominance relation, and the algorithms.
Webサービスの構成、複雑なシステムの設計、チーム編成など、多くのアプリケーションは、何らかの機能要件を満たすオブジェクトまたはエンティティのコレクションを識別する手法に依存しています。機能要件を満たすコレクションの中で、コレクションの非機能的特性を記述する属性の集合に対するユーザーの選好に関して最適な1つ以上のコレクションを識別することがしばしば必要になります。本稿では、ユーザーが属性間の相対的な重要性と、各属性の評価に対する質的な選好を表現できる形式論を開発します。また、コレクションを構成するオブジェクトの属性に対する選好の観点から、オブジェクトのコレクションを比較できる優位関係を定義します。優位関係のいくつかの重要な特性を確立します。特に、属性内選好関係が厳密な半順序であり、相対的な重要度の選好関係が区間順序である場合、優位関係は厳密な半順序であることを示します。本稿では、この優位関係を用いて最も選好されるコレクションの集合を識別するアルゴリズムを提供します。特定の条件下では、アルゴリズムは最も好ましいコレクションのみ（健全）、すべて（完全）、または少なくとも1つ（弱完全）を返すことが保証されることを示します。提案されたアルゴリズムを、（a）アルゴリズムによって生成されるソリューションの品質（最も好ましいソリューションの数）、および（b）パフォーマンスと効率に関して比較するシミュレーション実験の結果を示します。また、実験結果から示唆された、ユーザーの嗜好、優位関係、およびアルゴリズムの特性に関連するいくつかの興味深い仮説についても検討します。
Topological Value Iteration Algorithms
位相的値反復アルゴリズム
Value iteration is a powerful yet inefficient algorithm for Markov decision processes (MDPs) because it puts the majority of its effort into backing up the entire state space, which turns out to be unnecessary in many cases. In order to overcome this problem, many approaches have been proposed. Among them, ILAO* and variants of RTDP are state-of-the-art ones. These methods use reachability analysis and heuristic search to avoid some unnecessary backups. However, none of these approaches build the graphical structure of the state transitions in a pre-processing step or use the structural information to systematically decompose a problem, whereby generating an intelligent backup sequence of the state space. In this paper, we present two optimal MDP algorithms. The first algorithm, topological value iteration (TVI), detects the structure of MDPs and backs up states based on topological sequences. It (1) divides an MDP into strongly-connected components (SCCs), and (2) solves these components sequentially. TVI outperforms VI and other state-of-the-art algorithms vastly when an MDP has multiple, close-to-equal-sized SCCs. The second algorithm, focused topological value iteration (FTVI), is an extension of TVI. FTVI restricts its attention to connected components that are relevant for solving the MDP. Specifically, it uses a small amount of heuristic search to eliminate provably sub-optimal actions; this pruning allows FTVI to find smaller connected components, thus running faster. We demonstrate that FTVI outperforms TVI by an order of magnitude, averaged across several domains. Surprisingly, FTVI also significantly outperforms popular `heuristically-informed’ MDP algorithms such as ILAO*, LRTDP, BRTDP and Bayesian-RTDP in many domains, sometimes by as much as two orders of magnitude. Finally, we characterize the type of domains where FTVI excels — suggesting a way to an informed choice of solver.
値反復法は、マルコフ決定過程（MDP）に対する強力ですが非効率的なアルゴリズムです。これは、状態空間全体のバックアップにほとんどの労力を費やしているためですが、多くの場合、これは不要であることが判明しています。この問題を克服するために、多くのアプローチが提案されています。その中でも、ILAO*とRTDPの変種は最先端のものです。これらの方法は、到達可能性分析とヒューリスティックサーチを使用して、不要なバックアップを回避します。しかし、これらのアプローチのいずれも、前処理ステップで状態遷移のグラフィカル構造を構築したり、構造情報を使用して問題を体系的に分解し、状態空間のインテリジェントなバックアップシーケンスを生成したりしていません。本稿では、2つの最適なMDPアルゴリズムを紹介します。最初のアルゴリズムである位相的値反復法（TVI）は、MDPの構造を検出し、位相シーケンスに基づいて状態をバックアップします。これは、（1）MDPを強く連結されたコンポーネント（SCC）に分割し、（2）これらのコンポーネントを順番に解きます。TVIは、MDPが複数のほぼ等しいサイズのSCCを持つ場合、VIやその他の最先端アルゴリズムを大幅に上回ります。2つ目のアルゴリズムであるフォーカストポロジカルバリューイテレーション（FTVI）は、TVIの拡張版です。FTVIは、MDPを解くのに関連する連結成分にのみ注目します。具体的には、少量のヒューリスティックサーチを用いて、明らかに最適ではないアクションを排除します。この枝刈りにより、FTVIはより小さな連結成分を見つけることができるため、実行速度が向上します。FTVIは、複数のドメインを平均すると、TVIを1桁上回る性能を発揮することを実証しました。驚くべきことに、FTVIは、多くのドメインにおいて、ILAO*、LRTDP、BRTDP、Bayesian-RTDPなどの一般的な「ヒューリスティック情報に基づく」MDPアルゴリズムを大幅に上回り、場合によっては2桁も上回ります。最後に、FTVIが優れているドメインのタイプを特徴付け、情報に基づいたソルバーの選択方法を示します。
First-Order Stable Model Semantics and First-Order Loop Formulas
一階安定モデル意味論と一階ループ式
Lin and Zhao’s theorem on loop formulas states that in the propositional case the stable model semantics of a logic program can be completely characterized by propositional loop formulas, but this result does not fully carry over to the first-order case. We investigate the precise relationship between the first-order stable model semantics and first-order loop formulas, and study conditions under which the former can be represented by the latter. In order to facilitate the comparison, we extend the definition of a first-order loop formula which was limited to a nondisjunctive program, to a disjunctive program and to an arbitrary first-order theory. Based on the studied relationship we extend the syntax of a logic program with explicit quantifiers, which allows us to do reasoning involving non-Herbrand stable models using first-order reasoners. Such programs can be viewed as a special class of first-order theories under the stable model semantics, which yields more succinct loop formulas than the general language due to their restricted syntax.
LinとZhaoによるループ式に関する定理は、命題論理の場合、論理プログラムの安定モデル意味論は命題ループ式によって完全に特徴付けられるが、この結果は一階の場合には完全には適用できないことを述べています。本稿では、一階安定モデル意味論と一階ループ式の間の正確な関係を調査し、前者が後者によって表現可能な条件を考察します。比較を容易にするために、非選言プログラム、選言プログラム、および任意の一階理論に限定されていた一階ループ式の定義を拡張します。考察した関係に基づき、明示的な量化子を用いて論理プログラムの構文を拡張し、一階推論器を用いて非エルブラン安定モデルを含む推論を行うことができます。このようなプログラムは、安定モデル意味論の下では特別な一階理論クラスとみなすことができ、その制限された構文により、一般言語よりも簡潔なループ式が得られます。
Where Are the Hard Manipulation Problems?
困難な操作問題はどこにあるのか？
Voting is a simple mechanism to combine together the preferences of multiple agents. Unfortunately, agents may try to manipulate the result by mis-reporting their preferences. One barrier that might exist to such manipulation is computational complexity. In particular, it has been shown that it is NP-hard to compute how to manipulate a number of different voting rules. How- ever, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. In this paper, we show that empirical studies are useful in improving our understanding of this issue. We consider two settings which represent the two types of complexity results that have been identified in this area: manipulation with un-weighted votes by a single agent, and manipulation with weighted votes by a coalition of agents. In the first case, we consider Single Transferable Voting (STV), and in the second case, we consider veto voting. STV is one of the few voting rules used in practice where it is NP-hard to compute how a single agent can manipulate the result when votes are unweighted. It also appears one of the harder voting rules to manipulate since it involves multiple rounds. On the other hand, veto voting is one of the simplest representatives of voting rules where it is NP-hard to compute how a coalition of weighted agents can manipulate the result. In our experiments, we sample a number of distributions of votes including uniform, correlated and real world elections. In many of the elections in our experiments, it was easy to compute how to manipulate the result or to prove that manipulation was impossible. Even when we were able to identify a situation in which manipulation was hard to compute (e.g. when votes are highly correlated and the election is hung), we found that the computational difficulty of computing manipulations was somewhat precarious (e.g. with such hung elections, even a single uncorrelated voter was enough to make manipulation easy to compute).
投票は、複数のエージェントの選好を統合するシンプルなメカニズムです。しかしながら、エージェントは自身の選好を誤って報告することで結果を操作しようとする可能性があります。このような操作を阻む障壁の一つとして、計算複雑性があります。特に、複数の異なる投票ルールをどのように操作するかを計算することはNP困難であることが示されています。しかし、NP困難性は最悪のケースの計算複雑性を制限するだけです。最近の理論的結果は、実際には操作が容易な場合が多いことを示唆しています。本稿では、この問題の理解を深める上で実証研究が有用であることを示します。本研究では、この分野で特定されている2種類の計算複雑性の結果を表す2つの設定、すなわち、単一のエージェントによる重み付けされていない投票による操作と、複数のエージェントによる重み付けされた投票による操作について考察します。前者では、単一譲渡可能投票（STV）を、後者では拒否投票を考察します。STVは、投票に重み付けがない場合に単一のエージェントがどのように結果を操作できるかを計算することがNP困難となる、実際に使用される数少ない投票ルールの一つです。また、複数回のラウンドを伴うため、操作が難しい投票ルールの1つと思われます。一方、拒否権投票は、重み付けされたエージェントの連合がどのように結果を操作できるかを計算するのがNP困難である投票ルールの最も単純な代表例の1つです。私たちの実験では、均一選挙、相関選挙、現実世界の選挙など、さまざまな投票分布をサンプリングしました。実験の多くの選挙では、結果を操作する方法を計算し、操作が不可能であることを証明するのは簡単でした。操作の計算が難しい状況(たとえば、投票の相関が高く、選挙がハングしている場合)を特定できた場合でも、操作の計算の困難さはやや不安定であることがわかりました(たとえば、そのようなハング選挙では、相関のない投票者が1人いるだけでも、操作を簡単に計算できます)。