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

by

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

目次

論文

Probabilistic Description Logics for Subjective Uncertainty

Probabilistic Description Logics for Subjective Uncertainty / 主観的不確実性に対する確率的記述論理

We propose a family of probabilistic description logics (DLs) that are derived in a principled way from Halpern’s probabilistic first-order logic. The resulting probabilistic DLs have a two-dimensional semantics similar to temporal DLs and are well-suited for representing subjective probabilities. We carry out a detailed study of reasoning in the new family of logics, concentrating on probabilistic extensions of the DLs ALC and EL, and showing that the complexity ranges from PTime via ExpTime and 2ExpTime to undecidable.



我々は、ハルパーンの確率的一階述語論理から原理的に導出される確率的記述論理（DL）の族を提案します。結果として得られる確率的DLは、時間的DLに類似した2次元意味論を持ち、主観的確率の表現に適しています。我々は、この新しい論理族の推論について詳細な研究を行い、DL ALCとELの確率的拡張に焦点を合わせ、その複雑性がPTimeからExpTime、2ExpTimeを経て決定不能な範囲に及ぶことを示す。

Subset Selection Via Implicit Utilitarian Voting

Subset Selection Via Implicit Utilitarian Voting / 暗黙的功利主義投票によるサブセット選択

How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach — which we refer to as implicit utilitarian voting — assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of RoboVote.org, a not-for-profit website that helps users make group decisions via AI-driven voting methods.



投票者によって表明された順序的選好を、測定可能に優れた社会的選択へとどのように集約すべきだろうか？確立されたアプローチ（我々は暗黙的功利主義投票と呼ぶ）は、投票者が報告された順位付けを誘導する潜在的な効用関数を持っていると仮定し、功利主義的社会福祉を近似的に最大化する投票ルールを求める。我々はこのアプローチを、選択肢のサブセットを選択するルールの設計に拡張します。我々は、歪みと後悔という2つの尺度の観点から、最適（決定論的およびランダム）ルールのパフォーマンスに関する解析的境界を導出します。実証的結果は、後悔ベースのルールが歪みベースのルールよりも説得力があることを示しており、我々は最適（決定論的）後悔ベースのルールのスケーラブルな実装の開発に焦点を当てています。我々の手法は、AI駆動型投票方法を介してユーザーがグループ意思決定を行うのを支援する非営利ウェブサイトであるRoboVote.orgの設計と実装の基礎となっています。

Controlled School Choice with Soft Bounds and Overlapping Types

Controlled School Choice with Soft Bounds and Overlapping Types / ソフトバウンドと重複型を考慮した制御された学校選択

School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., financially-distressed and minority types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Furthermore, we introduce an extended model that can handle both type-specific ceilings and floors and propose a extended mechanism DA-OT* to handle the extended model. Computer simulation results illustrate that DA-OT outperforms an artificial cap mechanism where we set a hard-bound for each type in each school. DA-OT* can achieve stability in the extended model without sacrificing students welfare.



学校選択プログラムは、生徒/保護者に生徒が通う公立学校を選択する機会を与えるために実施されます。制御された学校選択プログラムは、通常は社会経済的地位の観点から、生徒の構成に関する分布制約を維持しながら、生徒/保護者に選択肢を提供する必要があります。これまでの研究では、生徒のタイプに基づいて優先順位を柔軟に変更するソフトバウンドを設定する方が、各タイプの受け入れ可能生徒数を厳密に制限するハードバウンドを設定するよりも適切であることがわかっています。ソフトバウンドが課され、1人の学生が複数のタイプ（例えば、経済的困窮者タイプとマイノリティタイプ）に属する可能性があるケースを検討します。まず、既存のモデルを単純に拡張したモデルを、互いに素なタイプに適用した場合、安定的なマッチングが存在しない可能性があることを示す。そこで、学校が各タイプに席を予約する代替モデルと代替安定性定義を提案します。このモデルでは安定的なマッチングが存在することが保証されていることを示し、重複タイプに対する延期受入れ（DA-OT）と呼ばれるメカニズムを開発します。DA-OTメカニズムは戦略証明であり、すべての安定的なマッチングの中で学生にとって最適なマッチングを実現します。さらに、タイプ固有の上限と下限の両方を処理できる拡張モデルを導入し、拡張モデルを処理するための拡張メカニズムDA-OT*を提案します。コンピュータシミュレーションの結果、DA-OTは、各学校の各タイプにハードバウンドを設定する人工的なキャップメカニズムよりも優れた性能を示す。DA-OT*は、学生の福祉を犠牲にすることなく、拡張モデルにおいて安定性を実現できます。

Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity

Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity / 整数計画法を用いたベイジアンネットワーク構造学習：多面体、ファセット、複雑性

The challenging task of learning structures of probabilistic graphical models is an important problem within modern AI research. Recent years have witnessed several major algorithmic advances in structure learning for Bayesian networks – arguably the most central class of graphical models – especially in what is known as the score-based setting. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP), is implemented in the GOBNILP system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the IP based approach to BNSL is still somewhat lacking. Understanding fundamental aspects of cutting planes and the related separation problem is important not only from a purely theoretical perspective, but also since it holds out the promise of further improving the efficiency of state-of-the-art approaches to solving BNSL exactly. In this paper, we make several theoretical contributions towards these goals: (i) we study the computational complexity of the separation problem, proving that the problem is NP-hard; (ii) we formalise and analyse the relationship between three key polytopes underlying the IP-based approach to BNSL; (iii) we study the facets of the three polytopes both from the theoretical and practical perspective, providing, via exhaustive computation, a complete enumeration of facets for low-dimensional family-variable polytopes; and, furthermore, (iv) we establish a tight connection of the BNSL problem to the acyclic subgraph problem.



確率的グラフィカルモデルの構造を学習するという困難なタスクは、現代のAI研究における重要な問題です。近年、グラフィカルモデルの最も中心的なクラスとも言えるベイジアンネットワークの構造学習において、特にスコアベース設定として知られるものにおいて、いくつかの主要なアルゴリズムの進歩が見られました。GOBNILPシステムには、整数計画法(IP)に基づく最適ベイジアンネットワーク構造学習(BNSL)への成功した一般的なアプローチが実装されています。最近のアルゴリズムの進歩にもかかわらず、BNSLへのIPベースのアプローチの基礎となる側面の理解は、現在まだいくらか不足しています。切断面と関連する分離問題の基本的な側面を理解することは、純粋に理論的な観点からだけでなく、BNSLを正確に解く最先端のアプローチの効率をさらに向上させる可能性を秘めているため、重要です。本稿では、これらの目標に向けていくつかの理論的な貢献を行います。(i)分離問題の計算複雑性を研究し、問題がNP困難であることを証明します。(ii) BNSLへのIPベースのアプローチの基礎となる3つの主要な多面体間の関係を定式化し、分析します。(iii) 3つの多面体のファセットを理論的および実践的観点から研究し、網羅的な計算によって、低次元族変数多面体のファセットの完全な列挙を提供します。さらに、(iv) BNSL問題と非巡回部分グラフ問題との密接な関連性を確立します。

DESPOT: Online POMDP Planning with Regularization

DESPOT: Online POMDP Planning with Regularization / DESPOT：正則化を用いたオンラインPOMDP計画

The partially observable Markov decision process (POMDP) provides a principled general framework for planning under uncertainty, but solving POMDPs optimally is computationally intractable, due to the “curse of dimensionality” and the “curse of history”. To overcome these challenges, we introduce the Determinized Sparse Partially Observable Tree (DESPOT), a sparse approximation of the standard belief tree, for online planning under uncertainty. A DESPOT focuses online planning on a set of randomly sampled scenarios and compactly captures the “execution” of all policies under these scenarios. We show that the best policy obtained from a DESPOT is near-optimal, with a regret bound that depends on the representation size of the optimal policy. Leveraging this result, we give an anytime online planning algorithm, which searches a DESPOT for a policy that optimizes a regularized objective function. Regularization balances the estimated value of a policy under the sampled scenarios and the policy size, thus avoiding overfitting. The algorithm demonstrates strong experimental results, compared with some of the best online POMDP algorithms available. It has also been incorporated into an autonomous driving system for real-time vehicle control. The source code for the algorithm is available online.



部分観測マルコフ決定過程（POMDP）は、不確実性下での計画のための原理的な一般枠組みを提供するが、「次元の呪い」と「履歴の呪い」のために、POMDPを最適に解くことは計算的に困難です。これらの課題を克服するために、我々は不確実性下でのオンライン計画のために、標準的なビリーフツリーのスパース近似であるDeterminized Sparse Partially Observable Tree（DESPOT）を導入します。DESPOTは、ランダムにサンプリングされたシナリオの集合にオンラインプランニングを集中させ、これらのシナリオにおけるすべてのポリシーの「実行」を簡潔に捉えます。DESPOTから得られる最良のポリシーは、最適ポリシーの表現サイズに依存する後悔境界を持つ、ほぼ最適なポリシーであることを示します。この結果を利用して、DESPOTから正規化された目的関数を最適化するポリシーを探索する、いつでも利用可能なオンラインプランニングアルゴリズムを提供します。正規化は、サンプリングされたシナリオにおけるポリシーの推定値とポリシーサイズのバランスをとることで、過適合を回避します。このアルゴリズムは、利用可能な最高のオンラインPOMDPアルゴリズムのいくつかと比較して、優れた実験結果を示しています。また、このアルゴリズムは、リアルタイム車両制御のための自動運転システムにも組み込まれています。このアルゴリズムのソースコードはオンラインで入手できます。

Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function

Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function / 2レベル構成チェックと頻度ベーススコアリング関数を用いた最小重み支配集合の局所探索

The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2FS, according to the names of the two ideas. The experimental results show that, CC2FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.



最小重み支配集合（MWDS）問題は、最小支配集合（MDS）問題の重要な一般化であり、幅広い応用が期待されています。本論文では、2つの新しいアイデアに基づいた、MWDS問題に対する新しい局所探索アルゴリズムを提案します。最初のアイデアは、2レベル構成チェック（CC2）と呼ばれるヒューリスティックです。これは、最近の強力な構成チェック戦略（CC）の新たなバリエーションであり、最近の探索経路を効果的に回避します。2つ目のアイデアは、頂点の発見頻度に基づく新しいスコアリング関数です。私たちのアルゴリズムは、2つのアイデアの名前にちなんでCC2FSと名付けられています。実験結果によると、CC2FSは、幅広いMWDSベンチマークにおいて、解の品質に関していくつかの最先端アルゴリズムよりもはるかに優れた性能を発揮します。

Computational Aspects of Nearly Single-Peaked Electorates

Computational Aspects of Nearly Single-Peaked Electorates / ほぼ単峰性の選挙区の計算的側面

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure.In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the single-peaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.



選挙結果を操作する方法として、操作、買収、そして統制は、よく研究されています。多くの投票ルールは、一般的には、これらの操作行為の一部に対して計算的に抵抗力があります。しかし、単峰性の選挙区に限定すると、これらのルールは突如として操作しやすくなります。最近、Faliszewski、Hemaspaandra、およびHemaspaandraは、ほぼ単峰性の選挙区における戦略的行動の計算複雑性を研究した。これらは、単峰性ではないが、ある距離尺度によれば単峰性に近い選挙区です。本稿では、単峰性に関するいくつかの新しい距離尺度を導入します。与えられたプロファイルがほぼ単峰性であるかどうかを判断することは、多くの場合NP完全であることを証明します。一つのケースとして、多項式時間アルゴリズムを提示します。単峰性の軸が与えられている場合、距離の決定は常に多項式時間で可能であることを示す。さらに、本稿で導入された新しい概念と文献の既存の概念との関係を調査します。

A Model-Theoretic View on Qualitative Constraint Reasoning

A Model-Theoretic View on Qualitative Constraint Reasoning / 定性制約推論に関するモデル理論的考察

Qualitative reasoning formalisms are an active research topic in artificial intelligence. In this survey we present a model-theoretic perspective on qualitative constraint reasoning and explain some of the basic concepts and results in an accessible way. In particular, we discuss the significance of omega-categoricity for qualitative reasoning, of primitive positive interpretations for complexity analysis, and of Datalog as a unifying language for describing local consistency algorithms.



定性的推論の形式主義は、人工知能において活発な研究テーマです。本稿では、定性的制約推論に関するモデル理論的視点を提示し、その基本概念と結果を分かりやすく解説します。特に、定性的推論におけるオメガ圏性、複雑性分析における原始的肯定的解釈、そして局所整合性アルゴリズムを記述するための統一言語としてのDatalogの重要性について論じます。

Dynamic Repositioning to Reduce Lost Demand in Bike Sharing Systems

Dynamic Repositioning to Reduce Lost Demand in Bike Sharing Systems / 自転車シェアリングシステムにおける需要喪失の削減のための動的再配置

Bike Sharing Systems (BSSs) are widely adopted in major cities of the world due to concerns associated with extensive private vehicle usage, namely, increased carbon emissions, traffic congestion and usage of nonrenewable resources. In a BSS, base stations are strategically placed throughout a city and each station is stocked with a pre-determined number of bikes at the beginning of the day. Customers hire the bikes from one station and return them at another station. Due to unpredictable movements of customers hiring bikes, there is either congestion (more than required) or starvation (fewer than required) of bikes at base stations. Existing data has shown that congestion/starvation is a common phenomenon that leads to a large number of unsatisfied customers resulting in a significant loss in customer demand. In order to tackle this problem, we propose an optimisation formulation to reposition bikes using vehicles while also considering the routes for vehicles and future expected demand. Furthermore, we contribute two approaches that rely on decomposability in the problem (bike repositioning and vehicle routing) and aggregation of base stations to reduce the computation time significantly. Finally, we demonstrate the utility of our approach by comparing against two benchmark approaches on two real-world data sets of bike sharing systems. These approaches are evaluated using a simulation where the movements of customers are generated from real-world data sets.



自転車シェアリングシステム（BSS）は、自家用車の大量使用に伴う炭素排出量の増加、交通渋滞、再生不可能な資源の使用といった懸念から、世界の主要都市で広く導入されています。BSSでは、ベースステーションが都市全体に戦略的に配置され、各ステーションには1日の始まりに所定数の自転車が備え付けられます。利用者は1つのステーションで自転車を借り、別のステーションに返却します。自転車を借りる利用者の動きは予測不可能であるため、ベースステーションでは自転車が混雑（必要以上に混雑）するか、不足（必要以上に不足）するかのいずれかが発生します。既存データによると、混雑/飢餓は一般的な現象であり、多くの顧客の不満を招き、顧客需要の大幅な損失につながります。この問題に対処するために、車両のルートと将来の需要予測も考慮しながら、車両を使用して自転車を再配置する最適化定式化を提案します。さらに、問題の分解可能性（自転車の再配置と車両のルーティング）と基地局の集約に依存する2つのアプローチを提供し、計算時間を大幅に短縮します。最後に、自転車シェアリングシステムの2つの実際のデータセットで2つのベンチマークアプローチと比較することにより、このアプローチの有用性を実証します。これらのアプローチは、顧客の動きが実際のデータセットから生成されるシミュレーションを使用して評価されます。

The Computational Complexity of Structure-Based Causality

The Computational Complexity of Structure-Based Causality / 構造に基づく因果関係の計算複雑性

Halpern and Pearl introduced a definition of actual causality; Eiter and Lukasiewicz showed that computing whether X = x is a cause of Y = y is NP-complete in binary models (where all variables can take on only two values) and Σ^P_2 -complete in general models. In the final version of their paper, Halpern and Pearl slightly modified the definition of actual cause, in order to deal with problems pointed out by Hopkins and Pearl. As we show, this modification has a nontrivial impact on the complexity of computing whether {X} = {x} is a cause of Y = y. To characterize the complexity, a new family D_k^P , k = 1, 2, 3, . . ., of complexity classes is introduced, which generalises the class DP introduced by Papadimitriou and Yannakakis (DP is just D_1^P). We show that the complexity of computing causality under the updated definition is D_2^P -complete.Chockler and Halpern extended the definition of causality by introducing notions of responsibility and blame, and characterized the complexity of determining the degree of responsibility and blame using the original definition of causality. Here, we completely characterize the complexity using the updated definition of causality. In contrast to the results on causality, we show that moving to the updated definition does not result in a difference in the complexity of computing responsibility and blame.



HalpernとPearlは実際の因果関係の定義を導入しました。EiterとLukasiewiczは、X = xがY = yの原因であるかどうかを計算することは、バイナリモデル（すべての変数が2つの値のみを取ることができる）ではNP完全であり、一般的なモデルではΣ^P_2完全であることを示しました。論文の最終版では、HalpernとPearlは、HopkinsとPearlが指摘した問題に対処するため、実際の原因の定義をわずかに修正しました。示すように、この修正は{X} = {x}がY = yの原因であるかどうかの計算の複雑性に重要な影響を及ぼします。この複雑性を特徴付けるために、PapadimitriouとYannakakisが導入したクラスDP (DPはD_1^Pに等しい)を一般化する、新しい複雑性クラスのファミリーD_k^P , k = 1, 2, 3, . . .,が導入されました。更新された定義のもとで因果関係を計算する複雑性がD_2^P完全であることを示します。ChocklerとHalpernは、責任と非難の概念を導入することで因果関係の定義を拡張し、元の因果関係の定義を使用して、責任と非難の程度を決定する複雑性を特徴付けました。ここでは、因果関係の更新された定義を使用して、複雑性を完全に特徴付けます。因果関係に関する結果とは対照的に、更新された定義に移行しても、責任と非難の計算の複雑さに違いは生じないことがわかります。

New Canonical Representations by Augmenting OBDDs with Conjunctive Decomposition

New Canonical Representations by Augmenting OBDDs with Conjunctive Decomposition / 連言分解を用いたOBDDの拡張による新しい標準表現

We identify two families of canonical knowledge compilation languages. Both families augment ROBDD with conjunctive decomposition bounded by an integer i ranging from 0 to ∞. In the former, the decomposition is finest and the decision respects a chain C of variables, while both the decomposition and decision of the latter respect a tree T of variables. In particular, these two families cover the three existing languages ROBDD, ROBDD with as many implied literals as possible, and AND/OR BDD. We demonstrate that each language in the first family is complete, while each one in the second family is incomplete with expressivity that does not decrease with incremental i. We also demonstrate that the succinctness does not decrease from the i-th language in the second family to the i-th language in the first family, and then to the (i+1)-th language in the first family. For the operating efficiency, on the one hand, we show that the two families of languages support a rich class of tractable logical operations, and particularly the tractability of each language in the second family is not less than that of ROBDD; and on the other hand, we introduce a new time efficiency criterion called rapidity which reflects the idea that exponential operations may be preferable if the language can be exponentially more succinct, and we demonstrate that the rapidity of each operation does not decrease from the i-th language in the second family to the i-th language in the first family, and then to the (i+1)-th language in the first family. Furthermore, we develop a compiler for the last language in the first family (i = ∞). Empirical results show that the compiler significantly advances the compiling efficiency of canonical representations. In fact, its compiling efficiency is comparable with that of the state-of-the-art compilers of non-canonical representations. We also provide a compiler for the i-th language in the first family by translating the last language in the first family into the i-th language (i < ∞). Empirical results show that we can sometimes use the i-th language instead of the last language without any obvious loss of space efficiency.



我々は標準的な知識コンパイル言語の2つのファミリを識別します。両方のファミリとも、0から ∞ までの整数iで区切られる連言分解でROBDDを拡張します。前者では分解が最も細かく、決定は変数のチェーンCに従うが、後者では分解と決定はどちらも変数のツリーTに従う。特に、これら2つのファミリは既存の3つの言語であるROBDD、可能な限り多くの暗黙のリテラルを含むROBDD、およびAND/OR BDDをカバーしています。最初のファミリの各言語は完全であるが、2番目のファミリの各言語は不完全であり、表現力がiの増分とともに低下しないことを示す。また、2番目のファミリのi番目の言語から最初のファミリのi番目の言語、さらに最初のファミリの(i+1)番目の言語まで簡潔性が低下しないことも示す。演算効率については、まず、2つの言語ファミリが豊富な種類の扱いやすい論理演算をサポートし、特に、2番目のファミリの各言語の扱いやすさはROBDDの扱いやすさに劣らないことを示します。また、言語が指数的に簡潔になる場合は指数演算が好ましいという考えを反映した、高速性と呼ばれる新しい時間効率基準を導入し、各演算の高速性が2番目のファミリのi番目の言語から1番目のファミリのi番目の言語、さらに1番目のファミリの(i+1)番目の言語まで低下しないことを示します。さらに、1番目のファミリの最後の言語(i =∞)用のコンパイラを開発します。実験結果により、このコンパイラによって標準表現のコンパイル効率が大幅に向上することが示されています。実際、そのコンパイル効率は、非標準表現の最先端のコンパイラに匹敵します。また、最初のファミリの最後の言語をi番目の言語（i <∞）に翻訳することにより、最初のファミリのi番目の言語用のコンパイラも提供します。実験結果から、明らかなメモリ効率の低下なしに、最後の言語の代わりにi番目の言語を使用できる場合があることが示されています。

Robots in Retirement Homes: Applying Off-the-Shelf Planning and Scheduling to a Team of Assistive Robots

Robots in Retirement Homes: Applying Off-the-Shelf Planning and Scheduling to a Team of Assistive Robots / 老人ホームにおけるロボット：既製の計画とスケジューリングを支援ロボットチームに適用する

This paper investigates three different technologies for solving a planning and scheduling problem of deploying multiple robots in a retirement home environment to assist elderly residents. The models proposed make use of standard techniques and solvers developed in AI planning and scheduling, with two primary motivations. First, to find a planning and scheduling solution that we can deploy in our real-world application. Second, to evaluate planning and scheduling technology in terms of the “model-and-solve” functionality that forms a major research goal in both domain-independent planning and constraint programming. Seven variations of our application are studied using the following three technologies: PDDL-based planning, time-line planning and scheduling, and constraint-based scheduling. The variations address specific aspects of the problem that we believe can impact the performance of the technologies while also representing reasonable abstractions of the real world application. We evaluate the capabilities of each technology and conclude that a constraint-based scheduling approach, specifically a decomposition using constraint programming, provides the most promising results for our application. PDDL-based planning is able to find mostly low quality solutions while the timeline approach was unable to model the full problem without alterations to the solver code, thus moving away from the model-and-solve paradigm. It would be misleading to conclude that constraint programming is “better” than PDDL-based planning in a general sense, both because we have examined a single application and because the approaches make different assumptions about the knowledge one is allowed to embed in a model. Nonetheless, we believe our investigation is valuable for AI planning and scheduling researchers as it highlights these different modelling assumptions and provides insight into avenues for the application of AI planning and scheduling for similar robotics problems. In particular, as constraint programming has not been widely applied to robot planning and scheduling in the literature, our results suggest significant untapped potential in doing so.



本論文では、高齢者ホーム環境に複数のロボットを配置して高齢者の入居者を支援する計画とスケジューリングの問題を解決するための3つの異なる技術を調査します。提案するモデルは、AI計画とスケジューリングで開発された標準的な手法とソルバーを利用しており、その主な目的は2つあります。1つ目は、実際のアプリケーションに展開できる計画とスケジューリングのソリューションを見つけることです。2つ目は、ドメイン非依存計画と制約プログラミングの両方の主要な研究目標である「モデル化と解決」機能の観点から、計画とスケジューリング技術を評価することです。PDDLベースの計画、タイムライン計画とスケジューリング、制約ベースのスケジューリングという3つの技術を用いて、アプリケーションの7つのバリエーションを研究します。これらのバリエーションは、技術のパフォーマンスに影響を与える可能性のある問題の特定の側面に対処すると同時に、実際のアプリケーションの適切な抽象化も表しています。各技術の能力を評価し、制約ベースのスケジューリング手法、特に制約プログラミングを用いた分解が、本アプリケーションにおいて最も有望な結果をもたらすという結論に至りました。PDDLベースのプランニングでは、主に低品質の解を見つけることができましたが、タイムラインアプローチではソルバーコードを変更せずに問題全体をモデル化することができず、モデル化と解決のパラダイムから逸脱してしまいました。制約プログラミングがPDDLベースのプランニングよりも一般的な意味で「優れている」と結論付けるのは誤解を招く恐れがあります。これは、本研究が単一のアプリケーションを対象としていること、そして各アプローチがモデルに埋め込むことができる知識について異なる仮定を置いていることの両方によるものです。とはいえ、本研究は、これらの異なるモデリングの仮定を明らかにし、類似のロボット工学問題へのAIプランニングとスケジューリングの適用の可能性についての洞察を提供するため、AIプランニングとスケジューリングの研究者にとって価値のあるものであると考えています。特に、制約プログラミングは文献においてロボットプランニングとスケジューリングに広く適用されていないため、本研究の結果は、その適用における大きな未開拓の可能性を示唆しています。

Explicit Document Modeling through Weighted Multiple-Instance Learning

Explicit Document Modeling through Weighted Multiple-Instance Learning / 重み付きマルチインスタンス学習による明示的文書モデリング

Representing documents is a crucial component in many NLP tasks, for instance predicting aspect ratings in reviews. Previous methods for this task treat documents globally, and do not acknowledge that target categories are often assigned by their authors with generally no indication of the specific sentences that motivate them. To address this issue, we adopt a weakly supervised learning model, which jointly learns to focus on relevant parts of a document according to the context along with a classifier for the target categories. Derived from the weighted multiple-instance regression (MIR) framework, the model learns decomposable document vectors for each individual category and thus overcomes the representational bottleneck in previous methods due to a fixed-length document vector. During prediction, the estimated relevance or saliency weights explicitly capture the contribution of each sentence to the predicted rating, thus offering an explanation of the rating. Our model achieves state-of-the-art performance on multi-aspect sentiment analysis, improving over several baselines. Moreover, the predicted saliency weights are close to human estimates obtained by crowdsourcing, and increase the performance of lexical and topical features for review segmentation and summarization.



文書の表現は、レビューにおける側面評価の予測など、多くのNLPタスクにおいて重要な要素です。このタスクにおける従来の手法は、文書を全体的に扱い、対象カテゴリは多くの場合、作成者によって割り当てられ、その動機となる特定の文が示されないという点を考慮していません。この問題に対処するため、我々は弱教師学習モデルを採用します。このモデルは、対象カテゴリの分類器と併せて、文脈に応じて文書の関連部分に焦点を当てることを共同学習します。重み付きマルチインスタンス回帰（MIR）フレームワークから派生したこのモデルは、個々のカテゴリごとに分解可能な文書ベクトルを学習することで、固定長の文書ベクトルに起因する従来の手法の表現上のボトルネックを克服します。予測中、推定された関連性または顕著性の重みは、予測された評価に対する各文の寄与を明示的に捉え、評価の説明を提供します。本モデルは、多側面感情分析において最先端の性能を達成し、複数のベースラインよりも向上しています。さらに、予測された顕著性の重みは、クラウドソーシングによって得られた人間の推定値に近いため、レビューのセグメンテーションと要約における語彙的特徴とトピック的特徴の性能が向上します。

A Probabilistic Formalization of the Appraisal for the OCC Event-Based Emotions

A Probabilistic Formalization of the Appraisal for the OCC Event-Based Emotions / OCCイベントベース感情の評価の確率的形式化

This article presents a logical formalization of the emotional appraisal theory, i.e., it formalizes the cognitive process of evaluation that elicits an emotion. This formalization is psychologically grounded on the OCC cognitive model of emotions. More specifically, we are interested in event-based emotions, i.e., emotions that are elicited by the evaluation of the consequences of an event that either happened or will happen. The formal modelling presented here is based on the AfPL Probabilistic Logic, a BDI-like probabilistic modal logic, which allows our model to verify whether the variables that determine the elicitation of emotions achieved the necessary threshold or not. The proposed logical formalization aims at addressing how the emotions are elicited by the agent cognitive mental states (desires, beliefs and intentions), and how to represent the intensity of the emotions. These are important initial points in the investigation of the dynamic interaction among emotions and other mental states.



本稿では、感情評価理論の論理的形式化、すなわち感情を喚起する評価の認知プロセスを形式化します。この形式化は、心理学的にはOCC感情認知モデルに基づいています。より具体的には、イベントベースの感情、すなわち発生した、または発生する可能性のあるイベントの結果の評価によって喚起される感情に注目しています。ここで提示する形式的モデリングは、BDIに似た確率様相論理であるAfPL確率論理に基づいており、これにより、感情の喚起を決定する変数が必要な閾値に達したかどうかをモデルで検証できます。提案される論理的形式化は、エージェントの認知的精神状態（欲求、信念、意図）によって感情がどのように喚起されるか、そして感情の強度をどのように表現するかを明らかにすることを目的としています。これらは、感情やその他の精神状態間の動的な相互作用を調査する上で重要な出発点となります。

Combinatorial Multi-armed Bandits for Real-Time Strategy Games

Combinatorial Multi-armed Bandits for Real-Time Strategy Games / リアルタイム戦略ゲームのための組み合わせ的多腕バンディット

Games with large branching factors pose a significant challenge for game tree search algorithms. In this paper, we address this problem with a sampling strategy for Monte Carlo Tree Search (MCTS) algorithms called “naive sampling”, based on a variant of the Multi-armed Bandit problem called “Combinatorial Multi-armed Bandits” (CMAB). We analyze the theoretical properties of several variants of naive sampling, and empirically compare it against the other existing strategies in the literature for CMABs. We then evaluate these strategies in the context of real-time strategy (RTS) games, a genre of computer games characterized by their very large branching factors. Our results show that as the branching factor grows, naive sampling outperforms the other sampling strategies.



大きな分岐係数を持つゲームは、ゲーム木探索アルゴリズムにとって大きな課題となります。本稿では、モンテカルロ木探索（MCTS）アルゴリズムのためのサンプリング戦略「ナイーブサンプリング」を用いてこの問題に対処します。この戦略は、「組み合わせ多腕バンディット」（CMAB）と呼ばれる多腕バンディット問題の変種に基づく。ナイーブサンプリングのいくつかの変種の理論的特性を分析し、CMABに関する文献に記載されている他の既存戦略と実証的に比較します。次に、これらの戦略を、非常に大きな分岐係数を特徴とするコンピュータゲームのジャンルであるリアルタイムストラテジー（RTS）ゲームにおいて評価します。結果は、分岐係数が大きくなるにつれて、ナイーブサンプリングが他のサンプリング戦略よりも優れた性能を示すことを示しています。

Tie-Breaking Strategies for Cost-Optimal Best First Search

Tie-Breaking Strategies for Cost-Optimal Best First Search / コスト最適最良優先探索のためのタイブレーク戦略

Best-first search algorithms such as A* need to apply tie-breaking strategies in order to decide which node to expand when multiple search nodes have the same evaluation score. We investigate and improve tie-breaking strategies for cost-optimal search using A*. We first experimentally analyze the performance of common tie-breaking strategies that break ties according to the heuristic value of the nodes. We find that the tie-breaking strategy has a significant impact on search algorithm performance when there are 0-cost operators that induce large plateau regions in the search space. Based on this, we develop two new classes of tie-breaking strategies. We first propose a depth diversification strategy which breaks ties according to the distance from the entrance to the plateau, and then show that this new strategy significantly outperforms standard strategies on domains with 0-cost actions. Next, we propose a new framework for interpreting A* search as a series of satisficing searches within plateaus consisting of nodes with the same f-cost. Based on this framework, we investigate a second, new class of tie-breaking strategy, a multi-heuristic tie-breaking strategy which embeds inadmissible, distance-to-go variations of various heuristics within an admissible search. This is shown to further improve the performance in combination with the depth metric.



A*のような最良優先探索アルゴリズムは、複数の探索ノードが同じ評価値を持つ場合に、どのノードを拡張するかを決定するために、タイブレーク戦略を適用する必要があります。本研究では、A*を用いたコスト最適探索のためのタイブレーク戦略を調査し、改良します。まず、ノードのヒューリスティック値に基づいてタイブレークを判定する一般的なタイブレーク戦略の性能を実験的に分析します。その結果、探索空間に大きなプラトー領域を誘導する0コスト演算子が存在する場合、タイブレーク戦略が探索アルゴリズムの性能に大きな影響を与えることが判明した。これに基づき、2つの新しいタイブレーク戦略クラスを開発します。まず、プラトーの入口からの距離に基づいてタイブレークを判定する深さ多様化戦略を提案し、この新しい戦略が0コストアクションを含む領域において標準的な戦略を大幅に上回る性能を示す。次に、A*探索を、同じfコストを持つノードからなるプラトー内での一連の満足探索として解釈するための新しい枠組みを提案します。この枠組みに基づき、我々は2つ目の新しい種類のタイブレーク戦略、すなわち、様々なヒューリスティックの許容されない残り距離のバリエーションを許容可能な探索内に組み込むマルチヒューリスティック・タイブレーク戦略を調査します。これは、深度メトリックと組み合わせることで性能をさらに向上させることが示されています。

A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing

A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing / 遷移に基づく自然言語処理のためのニューラル確率的構造化予測法

We propose a neural probabilistic structured-prediction method for transition-based natural language processing, which integrates beam search and contrastive learning. The method uses a global optimization model, which can leverage arbitrary features over non-local context. Beam search is used for efficient heuristic decoding, and contrastive learning is performed for adjusting the model according to search errors. When evaluated on both chunking and dependency parsing tasks, the proposed method achieves significant accuracy improvements over the locally normalized greedy baseline on the two tasks, respectively.



我々は、ビーム探索と対照学習を統合した、遷移ベースの自然言語処理のためのニューラル確率構造予測法を提案します。この手法は、非局所的なコンテキストにおいて任意の特徴を活用できるグローバル最適化モデルを用います。ビーム探索は効率的なヒューリスティックデコードに用いられ、対照学習は探索エラーに応じてモデルを調整するために行われます。チャンキングタスクと依存関係解析タスクの両方で評価したところ、提案手法は、それぞれ2つのタスクにおいて、局所的に正規化された貪欲法ベースラインと比較して大幅な精度向上を達成した。

Managing Different Sources of Uncertainty in a BDI Framework in a Principled Way with Tractable Fragments

Managing Different Sources of Uncertainty in a BDI Framework in a Principled Way with Tractable Fragments / 扱いやすいフラグメントを用いたBDIフレームワークにおける異なる不確実性要因の原理的な管理

The Belief-Desire-Intention (BDI) architecture is a practical approach for modelling large-scale intelligent systems. In the BDI setting, a complex system is represented as a network of interacting agents – or components – each one modelled based on its beliefs, desires and intentions. However, current BDI implementations are not well-suited for modelling more realistic intelligent systems which operate in environments pervaded by different types of uncertainty. Furthermore, existing approaches for dealing with uncertainty typically do not offer syntactical or tractable ways of reasoning about uncertainty. This complicates their integration with BDI implementations, which heavily rely on fast and reactive decisions. In this paper, we advance the state-of-the-art w.r.t. handling different types of uncertainty in BDI agents. The contributions of this paper are, first, a new way of modelling the beliefs of an agent as a set of epistemic states. Each epistemic state can use a distinct underlying uncertainty theory and revision strategy, and commensurability between epistemic states is achieved through a stratification approach. Second, we present a novel syntactic approach to revising beliefs given unreliable input. We prove that this syntactic approach agrees with the semantic definition, and we identify expressive fragments that are particularly useful for resource-bounded agents. Third, we introduce full operational semantics that extend CAN, a popular semantics for BDI, to establish how reasoning about uncertainty can be tightly integrated into the BDI framework. Fourth, we provide comprehensive experimental results to highlight the usefulness and feasibility of our approach, and explain how the generic epistemic state can be instantiated into various representations.



信念・欲求・意図（BDI）アーキテクチャは、大規模知能システムをモデリングするための実用的なアプローチです。BDI設定において、複雑なシステムは相互作用するエージェント（またはコンポーネント）のネットワークとして表現され、各エージェントは自身の信念、欲求、意図に基づいてモデル化されます。しかし、現在のBDI実装は、様々な種類の不確実性が蔓延する環境で動作する、より現実的な知的システムのモデル化には適していません。さらに、不確実性に対処するための既存のアプローチは、通常、不確実性について構文的かつ扱いやすい推論方法を提供していません。このため、迅速かつ反応的な意思決定に大きく依存するBDI実装との統合が複雑になっています。本論文では、BDIエージェントにおける様々な種類の不確実性の処理に関する最先端の研究成果を発展させます。本論文の貢献は、第一に、エージェントの信念を認識状態の集合としてモデル化する新しい手法です。各認識状態は、それぞれ異なる基礎となる不確実性理論と修正戦略を用いることができ、認識状態間の通約可能性は層別化アプローチによって実現されます。第二に、信頼できない入力が与えられた場合に信念を修正するための新しい構文的アプローチを提示します。この統語的アプローチが意味的定義と一致することを証明し、特にリソース制約型エージェントにとって有用な表現的フラグメントを特定します。第三に、BDIの一般的な意味論であるCANを拡張した完全な操作的意味論を導入し、不確実性に関する推論をBDIフレームワークに緊密に統合する方法を確立します。第四に、包括的な実験結果を示し、本アプローチの有用性と実現可能性を明らかにし、一般的な認識状態を様々な表現にインスタンス化する方法を説明します。

Some Properties of Batch Value of Information in the Selection Problem

Some Properties of Batch Value of Information in the Selection Problem / いくつかの特性選択問題における情報のバッチ価値

Given a set of items of unknown utility, we need to select one with a utility as high as possible (the selection problem). Measurements (possibly noisy) of item values prior to selection are allowed, at a known cost. The goal is to optimize the overall sequential decision process of measurements and selection.Value of information (VOI) is a well-known scheme for selecting measurements, but the intractability of the problem typically leads to using myopic VOI estimates. Other schemes have also been proposed, some with approximation guarantees, based on submodularity criteria. However, it was observed that the VOI is not submodular in general. In this paper we examine theoretical properties of VOI for the selection problem, and identify cases of submodularity and supermodularity. We suggest how to use these properties to compute approximately optimal measurement batch policies, with an example based on a wine selection problem.



効用が未知のアイテムのセットが与えられたとき、私たちは可能な限り高い効用を持つものを一つ選択する必要がある(選択問題)。選択前のアイテムの値の測定(ノイズが含まれる可能性もある)は、既知のコストで許可されます。目標は、測定と選択の全体的な順次的な決定プロセスを最適化することです。情報価値(VOI)は、測定を選択するためのよく知られた手法であるが、問題の扱いにくさから、通常は近視眼的なVOI推定値を使用することになります。他の手法も提案されており、その中にはサブモジュラリティ基準に基づく、近似保証付きのものもあります。しかし、VOIは一般にサブモジュラではないことが観察されています。本稿では、選択問題に対するVOIの理論的特性を調べ、サブモジュラリティとスーパーモジュラリティのケースを特定します。ワインの選択問題に基づく例を用いて、これらの特性を使用して近似的に最適な測定バッチ ポリシーを計算する方法を提案します。

Randomized Social Choice Functions Under Metric Preferences

Randomized Social Choice Functions Under Metric Preferences / メトリクス選好に基づくランダム化社会選択関数

We determine the quality of randomized social choice algorithms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the algorithms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between the expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized algorithms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic algorithms.



エージェントがメトリクス選好を持つ設定において、ランダム化社会選択アルゴリズムの品質を決定します。各エージェントはそれぞれの選択肢に対してコストを持ち、これらのコストがメトリクスを形成します。これらのコストはアルゴリズム（場合によってはエージェント自身も）にとって未知であると仮定します。つまり、最適な選択肢、すなわちエージェントの総コスト（またはエージェントコストの中央値）を最小化する選択肢を単純に選択することはできない。しかし、エージェントはメトリクス空間によって誘導される順序選好を知っていると仮定します。我々は、この順序情報のみを必要とし、メトリクスから得られるコストに関して期待値が良好な選択肢を選択するランダム化社会選択関数を検証します。ランダム化社会選択関数の良否を定量化するために、選択された選択肢の期待コストと最適な選択肢のコストとの間の最悪ケース比である歪みを上限とします。我々は、一般的なメトリクスと重要な特殊なケースの両方について、様々なランダム化アルゴリズムに対する新たな歪みの上限を提示します。我々の結果は、決定論的アルゴリズムと比較して歪みが大幅に改善されることを示しています。

Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning

Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning / 機械学習による木分解における動的計画法の効率改善

Dynamic Programming (DP) over tree decompositions is a well-established method to solve problems – that are in general NP-hard – efficiently for instances of small treewidth. Experience shows that (i) heuristically computing a tree decomposition has negligible runtime compared to the DP step; and (ii) DP algorithms exhibit a high variance in runtime when using different tree decompositions; in fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging runtimes. We thus propose here a novel and general method that is based on selection of the best decomposition from an available pool of heuristically generated ones. For this purpose, we require machine learning techniques that provide automated selection based on features of the decomposition rather than on the actual problem instance. Thus, one main contribution of this work is to propose novel features for tree decompositions. Moreover, we report on extensive experiments in different problem domains which show a significant speedup when choosing the tree decomposition according to this concept over simply using an arbitrary one of the same width.



木分解に対する動的計画法(DP)は、一般にNP困難な問題を、木幅が狭い場合に効率的に解く確立された手法です。経験から、(i)木分解をヒューリスティックに計算すると、DPステップに比べて実行時間がごくわずかであること、(ii) DPアルゴリズムでは、異なる木分解を使用した場合に実行時間に大きなばらつきがあることがわかっています。実際、問題のインスタンスを考えると、同じ幅の分解であっても実行時間が大きく異なる可能性があります。そこで本稿では、ヒューリスティックに生成された分解の利用可能なプールから最適な分解を選択する、新しい一般的な手法を提案します。このためには、実際の問題インスタンスではなく、分解の特徴に基づいて自動的に選択を行う機械学習手法が必要です。したがって、本研究の主な貢献の1つは、木分解の新しい特徴を提案することです。さらに、我々は様々な問題領域における広範な実験について報告し、この概念に従ってツリー分解を選択すると、単に同じ幅の任意のツリー分解を使用する場合と比較して、大幅な速度向上が見られることを示した。

Logics of Common Ground

Logics of Common Ground / 共通基盤の論理

According to Clark’s seminal work on common ground and grounding, participants collaborating in a joint activity rely on their shared information, known as common ground, to perform that activity successfully, and continually align and augment this information during their collaboration. Similarly, teams of human and artificial agents require common ground to successfully participate in joint activities. Indeed, without appropriate information being shared, using agent autonomy to reduce the workload on humans may actually increase workload as the humans seek to understand why the agents are behaving as they are. While many researchers have identified the importance of common ground in artificial intelligence, there is no precise definition of common ground on which to build the foundational aspects of multi-agent collaboration. In this paper, building on previously-defined modal logics of belief, we present logic definitions for four different types of common ground. We define modal logics for three existing notions of common ground and introduce a new notion of common ground, called salient common ground. Salient common ground captures the common ground of a group participating in an activity and is based on the common ground that arises from that activity as well as on the common ground they shared prior to the activity. We show that the four definitions share some properties, and our analysis suggests possible refinements of the existing informal and semi-formal definitions.



クラークの共通基盤とグラウンディングに関する先駆的な研究によれば、共同活動に参加する参加者は、共通基盤として知られる共有情報に依拠してその活動を成功させ、共同作業中にこの情報を継続的に調整・拡張します。同様に、人間と人工エージェントのチームが共同活動に成功するために共通基盤が必要です。実際、適切な情報が共有されていない場合、エージェントの自律性を利用して人間の作業負荷を軽減すると、人間はエージェントがなぜそのように行動しているのかを理解しようとするため、実際には作業負荷が増加する可能性があります。多くの研究者が人工知能における共通基盤の重要性を認識しているものの、マルチエージェントコラボレーションの基礎となる共通基盤の正確な定義は存在しない。本稿では、これまでに定義された信念の様相論理に基づき、4つの異なるタイプの共通基盤の論理定義を提示します。我々は、既存の共通基盤に関する3つの概念に対して様相論理を定義し、顕著な共通基盤と呼ばれる新しい共通基盤の概念を導入します。顕著な共通基盤とは、ある活動に参加する集団の共通基盤を捉え、その活動から生じる共通基盤と、活動以前に共有されていた共通基盤の両方に基づくものです。4つの定義がいくつかの特性を共有していることを示し、分析によって既存の非公式および準公式の定義の改良の可能性を示唆します。

Encoding Domain Transitions for Constraint-Based Planning

Encoding Domain Transitions for Constraint-Based Planning / 制約ベース計画のためのドメイン遷移の符号化

We describe a constraint-based automated planner named Transition Constraints for Parallel Planning (TCPP). TCPP constructs its constraint model from a redefined version of the domain transition graphs (DTG) of a given planning problem. TCPP encodes state transitions in the redefined DTGs by using table constraints with cells containing don’t cares or wild cards. TCPP uses Minion the constraint solver to solve the constraint model and returns a parallel plan. We empirically compare TCPP with the other state-of-the-art constraint-based parallel planner PaP2. PaP2 encodes action successions in the finite state automata (FSA) as table constraints with cells containing sets of values. PaP2 uses SICStus Prolog as its constraint solver. We also improve PaP2 by using dont cares and mutex constraints. Our experiments on a number of standard classical planning benchmark domains demonstrate TCPP’s efficiency over the original PaP2 running on SICStus Prolog and our reconstructed and enhanced versions of PaP2 running on Minion.



我々は、並列プランニングのための遷移制約(TCPP)という制約ベースの自動プランナーについて説明します。TCPPは、特定のプランニング問題のドメイン遷移グラフ(DTG)の再定義バージョンから制約モデルを構築します。TCPPは、セルにドント ケアまたはワイルド カードを含むテーブル制約を使用して、再定義されたDTG内の状態遷移をエンコードします。TCPPは、制約ソルバーMinionを使用して制約モデルを解き、並列プランを返します。我々は、TCPPを他の最先端の制約ベースの並列プランナーPaP2と経験的に比較します。PaP2は、有限状態オートマトン(FSA)内のアクションの連続を、セルに値のセットを含むテーブル制約としてエンコードします。PaP2は、制約ソルバーとしてSICStus Prologを使用します。また、ドント ケア制約とミューテックス制約を使用してPaP2を改良します。標準的な古典的計画ベンチマークドメインを用いた実験により、TCPPはSICStus Prolog上で動作するオリジナルのPaP2およびMinion上で動作する再構築・拡張版のPaP2よりも効率的であることが実証されました。

参考文献

関連情報