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

by

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

目次

論文

Cooperative Monitoring to Diagnose Multiagent Plans

Cooperative Monitoring to Diagnose Multiagent Plans / マルチエージェント計画を診断するための協調モニタリング

Diagnosing the execution of a Multiagent Plan (MAP) means identifying and explaining action failures (i.e., actions that did not reach their expected effects). Current approaches to MAP diagnosis are substantially centralized, and assume that action failures are independent of each other.In this paper, the diagnosis of MAPs, executed in a dynamic and partially observable environment, is addressed in a fully distributed and asynchronous way; in addition, action failures are no longer assumed as independent of each other. The paper presents a novel methodology, named Cooperative Weak-Committed Monitoring (CWCM), enabling agents to cooperate while monitoring their own actions. Cooperation helps the agents to cope with very scarcely observable environments: what an agent cannot observe directly can be acquired from other agents. CWCM exploits nondeterministic action models to carry out two main tasks: detecting action failures and building trajectory-sets (i.e., structures representing the knowledge an agent has about the environment in the recent past). Relying on trajectory-sets, each agent is able to explain its own action failures in terms of exogenous events that have occurred during the execution of the actions themselves. To cope with dependent failures, CWCM is coupled with a diagnostic engine that distinguishes between primary and secondary action failures.An experimental analysis demonstrates that the CWCM methodology, together with the proposed diagnostic inferences, are effective in identifying and explaining action failures even in scenarios where the system observability is significantly reduced.



マルチエージェントプラン（MAP）の実行を診断することは、アクションの失敗（すなわち、期待された効果を達成できなかったアクション）を特定し、説明することを意味します。現在のMAP診断アプローチは実質的に集中化されており、アクションの失敗は互いに独立していると想定されています。本稿では、動的かつ部分的に観測可能な環境で実行されるMAPの診断を、完全に分散された非同期的な方法で扱います。さらに、アクションの失敗はもはや互いに独立しているとは想定されません。本稿では、エージェントが自身のアクションを監視しながら協力することを可能にする、協調的弱コミットモニタリング（CWCM）と呼ばれる新しい方法論を提示します。協力は、エージェントが観測可能性が非常に低い環境に対処するのに役立ちます。エージェントが直接観測できない情報は、他のエージェントから取得できます。CWCMは、非決定性アクションモデルを利用して、アクションの失敗の検出と軌跡セット（すなわち、エージェントが最近の環境について持つ知識を表す構造）の構築という2つの主要なタスクを実行します。各エージェントは、軌跡セットに基づいて、自身の行動の失敗を、その行動の実行中に発生した外生的イベントの観点から説明することができます。従属的な失敗に対処するため、CWCMは、一次的行動の失敗と二次的行動の失敗を区別する診断エンジンと結合されています。実験分析により、CWCM手法と提案された診断推論を組み合わせることで、システムの可観測性が大幅に低下したシナリオでも、行動の失敗を識別および説明するのに効果的であることが実証されています。

Text Rewriting Improves Semantic Role Labeling

Text Rewriting Improves Semantic Role Labeling / テキスト書き換えによる意味的役割ラベル付けの改善

Large-scale annotated corpora are a prerequisite to developing high-performance NLP systems. Such corpora are expensive to produce, limited in size, often demanding linguistic expertise. In this paper we use text rewriting as a means of increasing the amount of labeled data available for model training. Our method uses automatically extracted rewrite rules from comparable corpora and bitexts to generate multiple versions of sentences annotated with gold standard labels. We apply this idea to semantic role labeling and show that a model trained on rewritten data outperforms the state of the art on the CoNLL-2009 benchmark dataset.



大規模な注釈付きコーパスは、高性能NLPシステムの開発に不可欠です。このようなコーパスは作成コストが高く、サイズが限られており、多くの場合、言語の専門知識が求められます。本稿では、モデルトレーニングに利用可能なラベル付きデータの量を増やす手段として、テキスト書き換えを用います。本手法では、比較可能なコーパスとバイテキストから自動的に抽出された書き換え規則を用いて、ゴールドスタンダードラベルで注釈付けされた複数のバージョンの文を生成します。この考え方を意味役割ラベリングに適用し、書き換えデータで学習したモデルがCoNLL-2009ベンチマークデータセットにおいて最先端のモデルよりも優れた性能を示すことを示す。

Simple Regret Optimization in Online Planning for Markov Decision Processes

Simple Regret Optimization in Online Planning for Markov Decision Processes / マルコフ決定過程のオンライン計画における単純リグレット最適化

We consider online planning in Markov decision processes (MDPs). In online planning, the agent focuses on its current state only, deliberates about the set of possible policies from that state onwards and, when interrupted, uses the outcome of that exploratory deliberation to choose what action to perform next. Formally, the performance of algorithms for online planning is assessed in terms of simple regret, the agent’s expected performance loss when the chosen action, rather than an optimal one, is followed.To date, state-of-the-art algorithms for online planning in general MDPs are either best effort, or guarantee only polynomial-rate reduction of simple regret over time. Here we introduce a new Monte-Carlo tree search algorithm, BRUE, that guarantees exponential-rate and smooth reduction of simple regret. At a high level, BRUE is based on a simple yet non-standard state-space sampling scheme, MCTS2e, in which different parts of each sample are dedicated to different exploratory objectives. We further extend BRUE with a variant of “learning by forgetting.” The resulting parametrized algorithm, BRUE(alpha), exhibits even more attractive formal guarantees than BRUE. Our empirical evaluation shows that both BRUE and its generalization, BRUE(alpha), are also very effective in practice and compare favorably to the state-of-the-art.



マルコフ決定過程（MDP）におけるオンラインプランニングを考察します。オンラインプランニングでは、エージェントは現在の状態のみに焦点を合わせ、その状態以降の可能なポリシーの集合について熟考し、中断された場合は、その探索的熟考の結果を用いて次に実行するアクションを選択します。正式には、オンラインプランニングアルゴリズムの性能は、単純後悔、つまり最適なアクションではなく選択されたアクションを実行した場合のエージェントの期待される性能損失の観点から評価されます。現在、一般的なMDPにおけるオンラインプランニングの最先端のアルゴリズムは、ベストエフォート型か、時間の経過に伴う単純後悔の多項式速度削減のみを保証するかのいずれかです。本稿では、単純後悔の指数速度かつ滑らかな削減を保証する新しいモンテカルロ木探索アルゴリズムBRUEを紹介します。大まかに言うと、BRUEはシンプルながらも非標準的な状態空間サンプリング手法であるMCTS2eに基づいています。MCTS2eでは、各サンプルの異なる部分がそれぞれ異なる探索目的に割り当てられます。私たちはさらに、BRUEを「忘却による学習」の一種で拡張しました。その結果得られるパラメータ化アルゴリズムBRUE(alpha)は、BRUEよりもさらに魅力的な形式的保証を示します。私たちの実証的評価では、BRUEとその一般化であるBRUE(alpha)はどちらも実践において非常に効果的であり、最先端の手法に匹敵することが示されています。

Sensitivity of Diffusion Dynamics to Network Uncertainty

Sensitivity of Diffusion Dynamics to Network Uncertainty / ネットワークの不確実性に対する拡散ダイナミクスの感度

Simple diffusion processes on networks have been used to model, analyze and predict diverse phenomena such as spread of diseases, information and memes. More often than not, the underlying network data is noisy and sampled. This prompts the following natural question: how sensitive are the diffusion dynamics and subsequent conclusions to uncertainty in the network structure? In this paper, we consider two popular diffusion models: Independent cascade (IC) model and Linear threshold (LT) model. We study how the expected number of vertices that are influenced/infected, for particular initial conditions, are affected by network perturbations. Through rigorous analysis under the assumption of a reasonable perturbation model we establish the following main results. (1) For the IC model, we characterize the sensitivity to network perturbation in terms of the critical probability for phase transition of the network. We find that the expected number of infections is quite stable, unless the transmission probability is close to the critical probability. (2) We show that the standard LT model with uniform edge weights is relatively stable under network perturbations. (3) We study these sensitivity questions using extensive simulations on diverse real world networks and find that our theoretical predictions for both models match the observations quite closely. (4) Experimentally, the transient behavior, i.e., the time series of the number of infections, in both models appears to be more sensitive to network perturbations.



ネットワーク上の単純な拡散プロセスは、病気、情報、ミームなどの拡散といった多様な現象をモデル化し、分析し、予測するために利用されてきました。しかし、多くの場合、基盤となるネットワークデータはノイズが多く、サンプリングされたものです。そのため、当然ながら次のような疑問が生じます。拡散ダイナミクスとそれに続く結論は、ネットワーク構造の不確実性にどの程度影響されるのでしょうか。本稿では、独立カスケード（IC）モデルと線形閾値（LT）モデルという2つの一般的な拡散モデルを考察します。特定の初期条件において、影響を受ける/感染する頂点の期待数がネットワークの摂動によってどのように影響を受けるかを調べます。妥当な摂動モデルの仮定の下で厳密な解析を行い、以下の主要な結果を確立しました。(1) ICモデルでは、ネットワークの相転移の臨界確率によってネットワーク摂動に対する感受性を特徴づけます。感染の期待数は、伝播確率が臨界確率に近くない限り、極めて安定していることがわかりました。(2)均一なエッジウェイトを持つ標準的なLTモデルは、ネットワークの摂動に対して比較的安定していることを示します。(3)我々は、多様な現実世界のネットワーク上で広範なシミュレーションを用いてこれらの感度問題を研究し、両モデルに対する我々の理論的予測が観測結果と非常によく一致することを発見した。(4)実験的には、両モデルにおける過渡的挙動、すなわち感染数の時系列は、ネットワークの摂動に対してより敏感であるように思われます。

Entrenchment-Based Horn Contraction

Entrenchment-Based Horn Contraction / エントレンチメントベースのホーン収縮

The AGM framework is the benchmark approach in belief change. Since the framework assumes an underlying logic containing classical Propositional Logic, it can not be applied to systems with a logic weaker than Propositional Logic. To remedy this limitation, several researchers have studied AGM-style contraction and revision under the Horn fragment of Propositional Logic (i.e., Horn logic). In this paper, we contribute to this line of research by investigating the Horn version of the AGM entrenchment-based contraction. The study is challenging as the construction of entrenchment-based contraction refers to arbitrary disjunctions which are not expressible under Horn logic. In order to adapt the construction to Horn logic, we make use of a Horn approximation technique called Horn strengthening. We provide a representation theorem for the newly constructed contraction which we refer to as entrenchment-based Horn contraction. Ideally, contractions defined under Horn logic (i.e., Horn contractions) should be as rational as AGM contraction. We propose the notion of Horn equivalence which intuitively captures the equivalence between Horn contraction and AGM contraction. We show that, under this notion, entrenchment-based Horn contraction is equivalent to a restricted form of entrenchment-based contraction.



AGMフレームワークは、信念変化におけるベンチマークアプローチです。このフレームワークは、古典的な命題論理を含む基礎論理を前提としているため、命題論理よりも弱い論理を持つシステムには適用できない。この制限を改善するために、いくつかの研究者が、命題論理のホーンフラグメント（すなわち、ホーン論理）の下でのAGMスタイルの縮約と修正を研究してきた。本論文では、AGMエントレンチメントベースの縮約のホーンバージョンを調査することにより、この研究ラインに貢献します。エントレンチメントベースの縮約の構築は、ホーン論理では表現できない任意の選言を参照するため、この研究は困難です。この構築をホーン論理に適応させるために、ホーン強化と呼ばれるホーン近似手法を利用します。我々は、エントレンチメントベース・ホーン収縮と呼ぶ、新しく構築した収縮に対する表現定理を与える。理想的には、ホーン論理で定義された収縮（すなわち、ホーン収縮）は、AGM収縮と同じくらい合理的であるべきです。我々は、ホーン収縮とAGM収縮の同値性を直感的に捉えるホーン同値性の概念を提案します。この概念によれば、エントレンチメントベース・ホーン収縮は、エントレンチメントベース収縮の制限された形式と同等であることを示す。

Automaton Plans

Automaton Plans / オートマトン計画

Macros have long been used in planning to represent subsequences of operators. Macros can be used in place of individual operators during search, sometimes reducing the effort required to find a plan to the goal. Another use of macros is to compactly represent long plans. In this paper we introduce a novel solution concept called automaton plans in which plans are represented using hierarchies of automata. Automaton plans can be viewed as an extension of macros that enables parameterization and branching. We provide several examples that illustrate how automaton plans can be useful, both as a compact representation of exponentially long plans and as an alternative to sequential solutions in benchmark domains such as Logistics and Grid. We also compare automaton plans to other compact plan representations from the literature, and find that automaton plans are strictly more expressive than macros, but strictly less expressive than HTNs and certain representations allowing efficient sequential access to the operators of the plan.



マクロは、演算子のサブシーケンスを表現するために、長い間、計画に使用されてきました。マクロは、検索中に個々の演算子の代わりに使用することができ、目標への計画を見つけるために必要な労力を削減できる場合があります。マクロのもう1つの用途は、長い計画をコンパクトに表現することです。本稿では、オートマトンプランと呼ばれる新しいソリューション概念を紹介します。この概念では、プランはオートマトン階層を用いて表現されます。オートマトンプランは、パラメータ化と分岐を可能にするマクロの拡張とみなせる。本稿では、オートマトンプランが、指数関数的に長いプランのコンパクトな表現として、またロジスティクスやグリッドといったベンチマーク分野におけるシーケンシャルソリューションの代替として、どのように有用であるかを示すいくつかの例を提示します。また、オートマトンプランを文献で紹介されている他のコンパクトなプラン表現と比較した結果、オートマトンプランはマクロよりも表現力が高いものの、HTNやプランの演算子への効率的なシーケンシャルアクセスを可能にする特定の表現よりも表現力が劣ることが明らかになった。

Distributed Heuristic Forward Search for Multi-agent Planning

Distributed Heuristic Forward Search for Multi-agent Planning / マルチエージェント計画のための分散ヒューリスティックフォワードサーチ

This paper deals with the problem of classical planning for multiple cooperative agents who have private information about their local state and capabilities they do not want to reveal. Two main approaches have recently been proposed to solve this type of problem — one is based on reduction to distributed constraint satisfaction, and the other on partial-order planning techniques. In classical single-agent planning, constraint-based and partial-order planning techniques are currently dominated by heuristic forward search. The question arises whether it is possible to formulate a distributed heuristic forward search algorithm for privacy-preserving classical multi-agent planning. Our work provides a positive answer to this question in the form of a general approach to distributed state-space search in which each agent performs only the part of the state expansion relevant to it. The resulting algorithms are simple and efficient — outperforming previous algorithms by orders of magnitude — while offering similar flexibility to that of forward-search algorithms for single-agent planning. Furthermore, one particular variant of our general approach yields a distributed version of the A* algorithm that is the first cost-optimal distributed algorithm for privacy-preserving planning.



本論文は、自身のローカル状態と能力に関する秘密情報を秘匿する複数の協調エージェントのための古典的プランニング問題を取り扱う。この種の問題を解決するために、近年、主に2つのアプローチが提案されています。1つは分散制約充足への縮約に基づくもので、もう1つは半順序プランニング手法に基づくものです。古典的なシングルエージェントプランニングにおいて、制約ベースおよび半順序プランニング手法は、現在、ヒューリスティックなフォワードサーチによって支配されています。プライバシー保護を考慮した古典的なマルチエージェントプランニングのための分散ヒューリスティックなフォワードサーチアルゴリズムを定式化できるかどうかという疑問が生じる。本研究は、各エージェントが自身に関連する状態拡張の部分のみを実行する、分散状態空間探索への一般的なアプローチという形で、この疑問に肯定的な答えを提供します。結果として得られるアルゴリズムは単純かつ効率的であり、従来のアルゴリズムを桁違いに上回る性能を発揮すると同時に、シングルエージェントプランニングのためのフォワードサーチアルゴリズムと同等の柔軟性も提供します。さらに、本一般化アプローチの特定の変形は、プライバシー保護を考慮したプランニングのための最初のコスト最適分散アルゴリズムであるA*アルゴリズムの分散バージョンを生み出す。

Verification of Agent-Based Artifact Systems

Verification of Agent-Based Artifact Systems / エージェントベースアーティファクトシステムの検証

Artifact systems are a novel paradigm for specifying and implementing business processes described in terms of interacting modules called artifacts. Artifacts consist of data and lifecycles, accounting respectively for the relational structure of the artifacts states and their possible evolutions over time. In this paper we put forward artifact-centric multi-agent systems, a novel formalisation of artifact systems in the context of multi-agent systems operating on them. Differently from the usual process-based models of services, we give a semantics that explicitly accounts for the data structures on which artifact systems are defined.We study the model checking problem for artifact-centric multi-agent systems against specifications expressed in a quantified version of temporal-epistemic logic expressing the knowledge of the agents in the exchange. We begin by noting that the problem is undecidable in general. We identify a noteworthy class of systems that admit bisimilar, finite abstractions. It follows that we can verify these systems by investigating their finite abstractions; we also show that the corresponding model checking problem is EXPSPACE-complete. We then introduce artifact-centric programs, compact and declarative representations of the programs governing both the artifact system and the agents. We show that, while these in principle generate infinite-state systems, under natural conditions their verification problem can be solved on finite abstractions that can be effectively computed from the programs. We exemplify the theoretical results here pursued through a mainstream procurement scenario from the artifact systems literature.



アーティファクトシステムは、アーティファクトと呼ばれる相互作用するモジュールを用いて記述されるビジネスプロセスを仕様化し実装するための、新たなパラダイムです。アーティファクトはデータとライフサイクルで構成され、それぞれアーティファクトの状態の関連構造と、時間経過に伴うアーティファクトの進化の可能性を考慮します。本稿では、アーティファクトシステムを、その上で動作するマルチエージェントシステムの文脈において新たに形式化した、アーティファクト中心のマルチエージェントシステムを提案します。通常のプロセスベースのサービスモデルとは異なり、アーティファクトシステムが定義されるデータ構造を明示的に考慮したセマンティクスを提供します。本稿では、交換におけるエージェントの知識を表現する時相認識論的論理の量化版で表現された仕様に対する、アーティファクト中心のマルチエージェントシステムのモデル検査問題を考察します。まず、この問題が一般に決定不可能であることを指摘します。そして、類似した有限抽象化を許容する注目すべきシステムクラスを特定します。したがって、これらのシステムは、有限抽象化を調査することによって検証できます。また、対応するモデル検査問題がEXPSPACE完全であることを示します。次に、アーティファクトシステムとエージェントの両方を制御するプログラムの簡潔で宣言的な表現であるアーティファクト中心プログラムを紹介します。これらは原理的には無限状態システムを生成しますが、自然な条件下では、プログラムから効率的に計算できる有限抽象化に基づいて検証問題を解決できることを示します。ここでは、アーティファクトシステムの文献における主流の調達シナリオを通して追求した理論的結果を例示します。

A Novel SAT-Based Approach to Model Based Diagnosis

A Novel SAT-Based Approach to Model Based Diagnosis / モデルベース診断への新しいSATベースのアプローチ

This paper introduces a novel encoding of Model Based Diagnosis (MBD) to Boolean Satisfaction (SAT) focusing on minimal cardinality diagnosis. The encoding is based on a combination of sophisticated MBD preprocessing algorithms and the application of a SAT compiler which optimizes the encoding to provide more succinct CNF representations than obtained with previous works. Experimental evidence indicates that our approach is superior to all published algorithms for minimal cardinality MBD. In particular, we can determine, for the first time, minimal cardinality diagnoses for the entire standard ISCAS-85 and 74XXX benchmarks. Our results open the way to improve the state-of-the-art on a range of similar MBD problems.



本論文では、最小カーディナリティ診断に焦点を当てた、モデルベース診断（MBD）からブール満足度（SAT）への新しいエンコーディングを紹介します。このエンコーディングは、洗練されたMBD前処理アルゴリズムと、エンコーディングを最適化して、以前の研究よりも簡潔なCNF表現を提供するSATコンパイラの適用を組み合わせたものです。実験的証拠は、私たちのアプローチが、最小カーディナリティMBDのための公開されているすべてのアルゴリズムよりも優れていることを示しています。特に、標準ISCAS-85および74XXXベンチマーク全体について、初めて最小カーディナリティ診断を決定できます。私たちの研究結果は、様々な類似のMBD問題における最先端技術の改良への道を開くものです。

Scoring Functions Based on Second Level Score for k-SAT with Long Clauses

Scoring Functions Based on Second Level Score for k-SAT with Long Clauses / 長節を含むk-SATの第2レベルスコアに基づくスコアリング関数

It is widely acknowledged that stochastic local search (SLS) algorithms can efficiently find models for satisfiable instances of the satisfiability (SAT) problem, especially for random k-SAT instances. However, compared to random 3-SAT instances where SLS algorithms have shown great success, random k-SAT instances with long clauses remain very difficult. Recently, the notion of second level score, denoted as “score_2”, was proposed for improving SLS algorithms on long-clause SAT instances, and was first used in the powerful CCASat solver as a tie breaker.In this paper, we propose three new scoring functions based on score_2. Despite their simplicity, these functions are very effective for solving random k-SAT with long clauses. The first function combines score and score_2, and the second one additionally integrates the diversification property “age”. These two functions are used in developing a new SLS algorithm called CScoreSAT. Experimental results on large random 5-SAT and 7-SAT instances near phase transition show that CScoreSAT significantly outperforms previous SLS solvers. However, CScoreSAT cannot rival its competitors on random k-SAT instances at phase transition. We improve CScoreSAT for such instances by another scoring function which combines score_2 with age. The resulting algorithm HScoreSAT exhibits state-of-the-art performance on random k-SAT (k>3) instances at phase transition. We also study the computation of score_2, including its implementation and computational complexity.



確率的局所探索（SLS）アルゴリズムは、特にランダムk-SAT問題において、充足可能性（SAT）問題の充足可能なインスタンスのモデルを効率的に発見できることが広く認められています。しかし、SLSアルゴリズムが大きな成功を収めているランダム3-SAT問題と比較すると、長節SAT問題におけるランダムk-SAT問題は依然として非常に困難です。最近、「score_2」と呼ばれる第2レベルスコアの概念が、長節SAT問題におけるSLSアルゴリズムの改良のために提案され、強力なCCASatソルバーにおいてタイブレーカーとして初めて使用されました。本稿では、score_2に基づく3つの新しいスコアリング関数を提案します。これらの関数は単純であるにもかかわらず、長節SAT問題の解法に非常に効果的です。最初の関数はスコアとscore_2を組み合わせ、2番目の関数は多様化特性「age」をさらに統合します。これら2つの関数は、CScoreSATと呼ばれる新しいSLSアルゴリズムの開発に用いられます。フェーズ遷移近傍の大規模ランダム5-SATおよび7-SATインスタンスに対する実験結果から、CScoreSATは従来のSLSソルバーを大幅に上回る性能を示すことが示されました。しかし、フェーズ遷移におけるランダムk-SATインスタンスでは、CScoreSATは競合ソルバーに匹敵する性能を示しませんでした。そこで、score_2とageを組み合わせた別のスコアリング関数を導入することで、このようなインスタンスに対するCScoreSATの性能向上を図りました。結果として得られるアルゴリズムHScoreSATは、フェーズ遷移におけるランダムk-SAT（k>3）インスタンスにおいて、最先端の性能を発揮します。また、score_2の計算方法についても、実装と計算量を含めて検討しました。

Push and Rotate: a Complete Multi-agent Pathfinding Algorithm

Push and Rotate: a Complete Multi-agent Pathfinding Algorithm / プッシュアンドローテート：完全なマルチエージェント経路探索アルゴリズム

Multi-agent Pathfinding is a relevant problem in a wide range of domains, for example in robotics and video games research. Formally, the problem considers a graph consisting of vertices and edges, and a set of agents occupying vertices. An agent can only move to an unoccupied, neighbouring vertex, and the problem of finding the minimal sequence of moves to transfer each agent from its start location to its destination is an NP-hard problem.We present Push and Rotate, a new algorithm that is complete for Multi-agent Pathfinding problems in which there are at least two empty vertices. Push and Rotate first divides the graph into subgraphs within which it is possible for agents to reach any position of the subgraph, and then uses the simple push, swap, and rotate operations to find a solution; a post-processing algorithm is also presented that eliminates redundant moves. Push and Rotate can be seen as extending Luna and Bekris’s Push and Swap algorithm, which we showed to be incomplete in a previous publication.In our experiments we compare our approach with the Push and Swap, MAPP, and Bibox algorithms. The latter algorithm is restricted to a smaller class of instances as it requires biconnected graphs, but can nevertheless be considered state of the art due to its strong performance. Our experiments show that Push and Swap suffers from incompleteness, MAPP is generally not competitive with Push and Rotate, and Bibox is better than Push and Rotate on randomly generated biconnected instances, while Push and Rotate performs better on grids.



マルチエージェント経路探索は、ロボット工学やビデオゲームの研究など、幅広い分野で関連する問題です。正式には、この問題は頂点と辺からなるグラフと、頂点を占有するエージェントの集合を考慮します。エージェントは占有されていない近傍の頂点にのみ移動でき、各エージェントをスタート地点から目的地まで移動させる最短の移動シーケンスを見つける問題はNP困難問題です。本稿では、少なくとも2つの空の頂点があるマルチエージェント経路探索問題に完全に対応する新しいアルゴリズム、Push and Rotateを紹介します。Push and Rotateはまずグラフをサブグラフに分割し、そのサブグラフ内ではエージェントがサブグラフの任意の位置に到達できるようにします。次に、単純なプッシュ、スワップ、および回転操作を使用して解を見つけます。また、冗長な移動を排除する後処理アルゴリズムも紹介します。Push and Rotateは、以前の論文で不完全であることを示したLunaとBekrisのPush and Swapアルゴリズムを拡張したものと見ることができます。実験では、Push and Swap、MAPP、およびBiboxアルゴリズムと私たちのアプローチを比較します。後者のアルゴリズムは、2連結グラフを必要とするため、より小さなインスタンスクラスに制限されますが、それでも優れたパフォーマンスのため最先端と見なすことができます。実験では、Push and Swapには不完全性があり、MAPPは一般にPush and Rotateに匹敵せず、ランダムに生成された2連結インスタンスではBiboxがPush and Rotateよりも優れている一方で、Push and Rotateはグリッド上でより優れたパフォーマンスを発揮することが示されました。

Reasoning about Topological and Cardinal Direction Relations Between 2-Dimensional Spatial Objects

Reasoning about Topological and Cardinal Direction Relations Between 2-Dimensional Spatial Objects / 2次元空間オブジェクト間の位相関係と基本方向関係の推論

Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from multiple calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculi was very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning, the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. We consider two different interpretations of the RCC8 algebra, one uses a weak connectedness relation, the other uses a strong connectedness relation. In both interpretations, we show that reasoning with topological and directional information is decidable and remains in NP. Our computational complexity results unveil the significant differences between RA and CDC, and that between weak and strong RCC8 models. Take the combination of basic RCC8 and basic CDC constraints as an example: we show that the consistency problem is in P only when we use the strong RCC8 algebra and explicitly know the corresponding basic RA constraints.



定性的な空間計算の表現力を高めることは、アプリケーションの要件を満たすための重要なステップです。これは、複数の計算の関係を使用して空間情報を表現できる方法で既存の計算を組み合わせることで実現できます。大きな課題は、組み合わせた情報に対して推論する際に正確かつ完全な推論アルゴリズムを開発することです。これまでの研究では、主に、組み合わせた計算間の相互作用が小さい場合や、2つの計算のうちの1つが非常に単純な場合が研究されてきました。本稿では、拡張された空間オブジェクトの位相情報と方向情報の重要な組み合わせに取り組みます。定性的な空間推論で最もよく知られている計算のいくつか、位相情報を表現するためのRCC8代数と、方向情報を表現するための長方形代数(RA)および枢機卿方向計算(CDC)を組み合わせます。RCC8代数の2つの異なる解釈を検討します。1つは弱い連結関係を使用し、もう1つは強い連結関係を使用します。どちらの解釈でも、位相情報と方向情報による推論は決定可能であり、NPのままであることを示します。計算複雑度の結果は、RAとCDC、および弱いRCC8モデルと強いRCC8モデル間の重要な違いを明らかにします。基本的なRCC8制約と基本的なCDC制約の組み合わせを例に挙げると、強いRCC8代数を使用し、対応する基本的なRA制約を明示的に知っている場合にのみ、一貫性の問題がPにあることがわかります。

Optimal Scheduling of Contract Algorithms for Anytime Problem-Solving

Optimal Scheduling of Contract Algorithms for Anytime Problem-Solving / いつでも問題解決可能な契約アルゴリズムの最適スケジューリング

A contract algorithm is an algorithm which is given, as part of the input, a specified amount of allowable computation time. The algorithm must then complete its execution within the allotted time. An interruptible algorithm, in contrast, can be interrupted at an arbitrary point in time, at which point it must report its currently best solution. It is known that contract algorithms can simulate interruptible algorithms using iterative deepening techniques. This simulation is done at a penalty in the performance of the solution, as measured by the so-called acceleration ratio.In this paper we give matching (i.e., optimal) upper and lower bounds for the acceleration ratio under such a simulation. We assume the most general setting in which n problem instances must be solved by means of scheduling executions of contract algorithms in $m$ identical parallel processors. This resolves an open conjecture of Bernstein, Filkenstein, and Zilberstein who gave an optimal schedule under the restricted setting of round robin and length-increasing schedules, but whose optimality in the general unrestricted case remained open.Lastly, we show how to evaluate the average acceleration ratio of the class of exponential strategies in the setting of n problem instances and m parallel processors. This is a broad class of schedules that tend to be either optimal or near-optimal, for several variants of the basic problem.



契約アルゴリズムは、入力の一部として、許容される計算時間の指定された量が与えられるアルゴリズムです。アルゴリズムは割り当てられた時間内に実行を完了する必要があります。対照的に、割り込み可能なアルゴリズムは任意の時点で割り込むことができ、その時点で現在最適な解を報告する必要があります。契約アルゴリズムは、反復深化手法を使用して割り込み可能なアルゴリズムをシミュレートできることが知られています。このシミュレーションは、いわゆる加速率で測定されるソリューションのパフォーマンスのペナルティで実行されます。この論文では、このようなシミュレーションでの加速率の一致する（つまり最適な）上限と下限を示します。n個の問題インスタンスを、m個の同一の並列プロセッサで契約アルゴリズムの実行をスケジュールすることによって解決する必要があるという最も一般的な設定を前提としています。これにより、ラウンドロビンと長さ増加スケジュールという制限された設定の下では最適スケジュールを示したものの、一般的な制限のないケースでの最適性は未解決であった、Bernstein、Filkenstein、Zilbersteinの未解決予想が解決されます。最後に、n個の問題インスタンスとm個の並列プロセッサの設定において、指数戦略のクラスの平均加速率を評価する方法を示します。これは、基本問題のいくつかのバリエーションに対して、最適またはほぼ最適になる傾向がある広範なスケジュールのクラスです。

Iterative Plan Construction for the Workflow Satisfiability Problem

Iterative Plan Construction for the Workflow Satisfiability Problem / ワークフロー充足可能性問題のための反復計画構築

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan – an assignment of tasks to authorized users – such that all constraints are satisfied. It is natural to see the WSP as a subclass of the Constraint Satisfaction Problem (CSP) in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive is that the number of tasks is usually very small compared to the number of users, so it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks.This novel approach to the WSP, using techniques from CSP, has enabled us to design a generic algorithm which is FPT for several families of workflow constraints considered in the literature. Furthermore, we prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. Lastly, we identify a new FPT constraint language, user-independent constraints, that includes many of the constraints of interest in business processing systems. We demonstrate that our generic algorithm has provably optimal running time O*(2^(klog k)), for this language, where k is the number of tasks.



ワークフロー充足可能性問題(WSP)は、ビジネスルールによって定義された制約の下で、承認されたユーザーがタスクを実行する必要がある場合に常に発生する実用的な問題です。すべての制約が満たされるプラン(承認されたユーザーへのタスクの割り当て)が存在するかどうかを判断する必要があります。WSPを、変数がタスクでドメインがユーザーの集合である制約充足問題(CSP)のサブクラスと見なすのが自然です。WSPの特徴は、タスク数がユーザー数に比べて通常非常に少ないことです。そのため、WSPがタスク数によってパラメータ化された固定パラメータ制御可能（FPT）な制約言語を問うのが適切です。CSPの手法を用いたこのWSPへの新しいアプローチにより、文献で検討されているいくつかのワークフロー制約ファミリーに対してFPTとなる汎用アルゴリズムを設計することができました。さらに、FPT言語の和集合は、単純な互換性条件を満たす場合、FPTのままであることを証明しました。最後に、ビジネス処理システムで関心の高い多くの制約を含む、新しいFPT制約言語であるユーザー非依存制約を特定しました。この汎用アルゴリズムは、この言語に対して、O*(2^(klog k))という最適な実行時間を持つことを実証しました。ここで、kはタスク数です。

No Agent Left Behind: Dynamic Fair Division of Multiple Resources

No Agent Left Behind: Dynamic Fair Division of Multiple Resources / エージェントを置き去りにしない：複数リソースの動的公平分割

Recently fair division theory has emerged as a promising approach for allocation of multiple computational resources among agents. While in reality agents are not all present in the system simultaneously, previous work has studied static settings where all relevant information is known upfront. Our goal is to better understand the dynamic setting. On the conceptual level, we develop a dynamic model of fair division, and propose desirable axiomatic properties for dynamic resource allocation mechanisms. On the technical level, we construct two novel mechanisms that provably satisfy some of these properties, and analyze their performance using real data. We believe that our work informs the design of superior multiagent systems, and at the same time expands the scope of fair division theory by initiating the study of dynamic and fair resource allocation mechanisms.



最近、公平分割理論は、エージェント間で複数の計算資源を割り当てるための有望なアプローチとして浮上しました。実際には、すべてのエージェントが同時にシステム内に存在するわけではありませんが、これまでの研究では、すべての関連情報が事前にわかっている静的な設定が研究されていました。私たちの目標は、動的な設定をより深く理解することです。概念レベルでは、公平な分割の動的モデルを開発し、動的資源配分メカニズムに望ましい公理的性質を提案します。技術レベルでは、これらの性質のいくつかを証明可能に満たす2つの新しいメカニズムを構築し、実データを用いてその性能を分析します。本研究は、優れたマルチエージェントシステムの設計に役立つ情報を提供すると同時に、動的かつ公平な資源配分メカニズムの研究を先導することで、公平な分割理論の範囲を拡大するものであると考えています。

Using Meta-mining to Support Data Mining Workflow Planning and Optimization

Using Meta-mining to Support Data Mining Workflow Planning and Optimization / メタマイニングを用いたデータマイニングワークフロー計画と最適化のサポート

Knowledge Discovery in Databases is a complex process that involves many different data processing and learning operators. Today’s Knowledge Discovery Support Systems can contain several hundred operators. A major challenge is to assist the user in designing workflows which are not only valid but also — ideally — optimize some performance measure associated with the user goal. In this paper we present such a system. The system relies on a meta-mining module which analyses past data mining experiments and extracts meta-mining models which associate dataset characteristics with workflow descriptors in view of workflow performance optimization. The meta-mining model is used within a data mining workflow planner, to guide the planner during the workflow planning. We learn the meta-mining models using a similarity learning approach, and extract the workflow descriptors by mining the workflows for generalized relational patterns accounting also for domain knowledge provided by a data mining ontology. We evaluate the quality of the data mining workflows that the system produces on a collection of real world datasets coming from biology and show that it produces workflows that are significantly better than alternative methods that can only do workflow selection and not planning.



データベースにおける知識発見は、多くの異なるデータ処理および学習演算子を伴う複雑なプロセスです。今日の知識発見支援システムには、数百の演算子が含まれることがあります。大きな課題は、有効なだけでなく、理想的にはユーザーの目標に関連するいくつかのパフォーマンス測定を最適化するワークフローをユーザーが設計できるように支援することです。本稿では、そのようなシステムを紹介します。このシステムは、過去のデータマイニング実験を分析し、ワークフローパフォーマンスの最適化の観点からデータセットの特性をワークフロー記述子に関連付けるメタマイニングモデルを抽出するメタマイニングモジュールに依存しています。メタマイニングモデルは、データマイニングワークフロープランナー内で使用され、ワー​​クフローの計画中にプランナーをガイドします。類似性学習アプローチを使用してメタマイニングモデルを学習し、データマイニングオントロジーによって提供されるドメイン知識も考慮した一般化された関係パターンのワークフローをマイニングすることにより、ワークフロー記述子を抽出します。生物学分野の実世界データセットを用いて、システムが生成するデータマイニングワークフローの品質を評価し、ワークフロー選択のみが可能で計画はできない他の手法と比べて大幅に優れたワークフローを生成することを示します。

The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases

The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases / OWL 2 EL知識ベースにおける結合クエリとナビゲーションクエリへの回答の複雑さ

OWL 2 EL is a popular ontology language that supports role inclusions—that is, axioms that capture compositional properties of roles. Role inclusions closely correspond to context-free grammars, which was used to show that answering conjunctive queries (CQs) over OWL 2 EL knowledge bases with unrestricted role inclusions is undecidable. However, OWL 2 EL inherits from OWL 2 DL the syntactic regularity restriction on role inclusions, which ensures that role chains implying a particular role can be described using a finite automaton (FA). This is sufficient to ensure decidability of CQ answering; however, the FAs can be worst-case exponential in size so the known approaches do not provide a tight upper complexity bound.In this paper, we solve this open problem and show that answering CQs over OWL 2 EL knowledge bases is PSPACE-complete in combined complexity (i.e., the complexity measured in the total size of the input). To this end, we use a novel encoding of regular role inclusions using bounded-stack pushdown automata—that is, FAs extended with a stack of bounded size. Apart from theoretical interest, our encoding can be used in practical tableau algorithms to avoid the exponential blowup due to role inclusions. In addition, we sharpen the lower complexity bound and show that the problem is PSPACE-hard even if we consider only role inclusions as part of the input (i.e., the query and all other parts of the knowledge base are fixed). Finally, we turn our attention to navigational queries over OWL 2 EL knowledge bases, and we show that answering positive, converse-free conjunctive graph XPath queries is PSPACE-complete as well; this is interesting since allowing the converse operator in queries is known to make the problem EXPTIME-hard. Thus, in this paper we present several important contributions to the landscape of the complexity of answering expressive queries over description logic knowledge bases.



OWL 2 ELは、役割の包含（役割の組成特性を捉える公理）をサポートする、広く普及しているオントロジー言語です。役割の包含は文脈自由文法と密接に対応しており、文脈自由文法は、OWL 2 EL知識ベースにおいて、制限のない役割の包含を持つ連言クエリ（CQ）への回答が決定不能であることを示すために使用されました。しかし、OWL 2 ELは、OWL 2 DLから役割の包含に関する構文規則性制約を継承しており、これにより、特定の役割を暗示する役割連鎖を有限オートマトン（FA）を用いて記述できます。これは、CQ回答の決定可能性を保証するのに十分です。しかし、FAは最悪の場合指数関数的サイズになる可能性があるため、既知のアプローチでは厳密な複雑性の上限が提供されません。本稿では、この未解決問題を解決し、OWL 2 EL知識ベースを介してCQに回答することが、複合複雑性(つまり、入力の合計サイズで測定された複雑性)においてPSPACE完全であることを示します。このために、制限付きスタック プッシュダウン オートマトン、つまり制限されたサイズのスタックで拡張されたFAを使用した、通常の役割の包含の新しいエンコードを使用します。理論的な関心とは別に、このエンコードは、役割の包含による指数関数の爆発を回避するために実際のタブロー アルゴリズムで使用できます。さらに、複雑性の下限を明確にし、役割の包含のみを入力の一部として考慮した場合でも(つまり、クエリと知識ベースの他のすべての部分が固定されている)、問題がPSPACE困難であることを示します。最後に、OWL 2 EL知識ベースを介したナビゲーションクエリに注目し、肯定的かつ逆演算子を含まない連言グラフXPathクエリへの回答もPSPACE完全であることを示します。これは興味深い点です。なぜなら、クエリで逆演算子を許容すると、問題がEXPTIME困難になることが知られているからです。したがって、本稿では、記述論理知識ベースを介した表現力豊かなクエリへの回答の複雑さの全体像に対するいくつかの重要な貢献を示します。

On Minimum Representations of Matched Formulas

On Minimum Representations of Matched Formulas / 最小マッチングされた式の表現

A Boolean formula in conjunctive normal form (CNF) is called matched if the system of sets of variables which appear in individual clauses has a system of distinct representatives. Each matched CNF is trivially satisfiable (each clause can be satisfied by its representative variable). Another property which is easy to see, is that the class of matched CNFs is not closed under partial assignment of truth values to variables. This latter property leads to a fact (proved here) that given two matched CNFs it is co-NP complete to decide whether they are logically equivalent. The construction in this proof leads to another result: a much shorter and simpler proof of the fact that the Boolean minimization problem for matched CNFs is a complete problem for the second level of the polynomial hierarchy. The main result of this paper deals with the structure of clause minimum CNFs. We prove here that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.



連言正規形（CNF）のブール式は、個々の節に現れる変数集合の体系が、異なる代表変数の体系を持つ場合、マッチングされていると呼ばれます。マッチングされた各CNFは自明に充足可能（各節がその代表変数によって充足可能）です。もう一つ容易に理解できる特性は、マッチングされたCNFのクラスが、変数への真理値の部分的な割り当てに関して閉じていないことです。この後者の特性は、2つのマッチングされたCNFが与えられた場合、それらが論理的に同等かどうかを判断することはco-NP完全であるという事実（ここで証明）につながります。この証明における構成は、別の結果、すなわち、マッチドCNFのブール最小化問題が多項式階層の第2レベルにおける完全問題であるという事実の、はるかに短く簡潔な証明へと繋がります。本論文の主な結果は、節最小CNFの構造を扱っています。ブール関数fがマッチドCNFによる表現を許容する場合、fの節最小CNF表現はすべてマッチドであることを証明します。

On the Testability of BDI Agent Systems

On the Testability of BDI Agent Systems / BDIエージェントシステムのテスト可能性について

Before deploying a software system we need to assure ourselves (and stakeholders) that the system will behave correctly. This assurance is usually done by testing the system. However, it is intuitively obvious that adaptive systems, including agent-based systems, can exhibit complex behaviour, and are thus harder to test. In this paper we examine this “obvious intuition” in the case of Belief-Desire-Intention (BDI) agents. We analyse the size of the behaviour space of BDI agents and show that although the intuition is correct, the factors that influence the size are not what we expected them to be. Specifically, we found that the introduction of failure handling had a much larger effect on the size of the behaviour space than we expected. We also discuss the implications of these findings on the testability of BDI agents.



ソフトウェアシステムを導入する前に、システムが正しく動作するということを私たち自身（および利害関係者）に保証する必要があります。この保証は通常、システムのテストによって行われます。しかし、エージェントベースシステムを含む適応型システムは複雑な動作を示す可能性があり、そのためテストがより困難であることは直感的に明らかです。本稿では、信念・欲求・意図（BDI）エージェントを例に、この「明白な直感」を検証します。BDIエージェントの行動空間の大きさを分析し、直感は正しいものの、大きさに影響を与える要因は予想とは異なることを示します。具体的には、障害処理の導入が行動空間の大きさに予想よりもはるかに大きな影響を与えることがわかりました。また、これらの結果がBDIエージェントのテスト可能性に及ぼす影響についても考察します。

Tutorial on Structured Continuous-Time Markov Processes

Tutorial on Structured Continuous-Time Markov Processes / 構造化連続時間マルコフ過程のチュートリアル

A continuous-time Markov process (CTMP) is a collection of variables indexed by a continuous quantity, time. It obeys the Markov property that the distribution over a future variable is independent of past variables given the state at the present time. We introduce continuous-time Markov process representations and algorithms for filtering, smoothing, expected sufficient statistics calculations, and model estimation, assuming no prior knowledge of continuous-time processes but some basic knowledge of probability and statistics. We begin by describing “flat” or unstructured Markov processes and then move to structured Markov processes (those arising from state spaces consisting of assignments to variables) including Kronecker, decision-diagram, and continuous-time Bayesian network representations. We provide the first connection between decision-diagrams and continuous-time Bayesian networks.



連続時間マルコフ過程（CTMP）は、連続量である時間でインデックス付けされた変数の集合です。CTMPは、現在の状態を与えられた場合、将来の変数の分布は過去の変数とは独立であるというマルコフ性に従います。連続時間マルコフ過程の表現と、フィルタリング、平滑化、期待十分統計量計算、モデル推定のためのアルゴリズムを紹介します。連続時間過程に関する事前知識は不要ですが、確率と統計に関する基本的な知識はある程度必要です。まず、「平坦」または非構造化マルコフ過程について説明し、次にクロネッカー、決定図、連続時間ベイジアンネットワーク表現を含む構造化マルコフ過程（変数への割り当てからなる状態空間から生じるもの）について説明します。決定図と連続時間ベイジアンネットワークの最初の関連を示します。

BDD Ordering Heuristics for Classical Planning

BDD Ordering Heuristics for Classical Planning / 古典的計画のためのBDD順序付けヒューリスティック

Symbolic search using binary decision diagrams (BDDs) can often save large amounts of memory due to its concise representation of state sets. A decisive factor for this method’s success is the chosen variable ordering. Generally speaking, it is plausible that dependent variables should be brought close together in order to reduce BDD sizes. In planning, variable dependencies are typically captured by means of causal graphs, and in preceding work these were taken as the basis for finding BDD variable orderings. Starting from the observation that the two concepts of “dependency” are actually quite different, we introduce a framework for assessing the strength of variable ordering heuristics in sub-classes of planning. It turns out that, even for extremely simple planning tasks, causal graph based variable orders may be exponentially worse than optimal.Experimental results on a wide range of variable ordering variants corroborate our theoretical findings. Furthermore, we show that dynamic reordering is much more effective at reducing BDD size, but it is not cost-effective due to a prohibitive runtime overhead. We exhibit the potential of middle-ground techniques, running dynamic reordering until simple stopping criteria hold.



二分決定図（BDD）を用いたシンボリック探索は、状態集合の表現が簡潔であるため、多くの場合、大量のメモリを節約できます。この手法の成功を左右する決定的な要因は、選択された変数の順序です。一般的に、BDDのサイズを縮小するためには、従属変数を互いに近づける必要があると考えられます。計画においては、変数の依存関係は通常、因果グラフによって表されます。先行研究では、因果グラフがBDD変数の順序付けの基礎として用いられていました。「依存性」という2つの概念は実際には全く異なるという観察から出発し、プランニングのサブクラスにおける変数順序付けヒューリスティックの強度を評価するためのフレームワークを導入します。極めて単純なプランニングタスクであっても、因果グラフに基づく変数順序付けは最適な結果よりも指数関数的に劣る可能性があることが判明した。様々な変数順序付けのバリエーションを用いた実験結果は、我々の理論的発見を裏付けています。さらに、動的な順序付けはBDDのサイズ削減に非常に効果的であるものの、実行時のオーバーヘッドが大きすぎるため費用対効果が低いことを示す。我々は、単純な停止基準が満たされるまで動的な順序付けを実行するという、中間的な手法の可能性を示す。

A Hidden Markov Model-Based Acoustic Cicada Detector for Crowdsourced Smartphone Biodiversity Monitoring

A Hidden Markov Model-Based Acoustic Cicada Detector for Crowdsourced Smartphone Biodiversity Monitoring / クラウドソーシングによるスマートフォン生物多様性モニタリングのための隠れマルコフモデルに基づく音響セミ検出器

In recent years, the field of computational sustainability has striven to apply artificial intelligence techniques to solve ecological and environmental problems. In ecology, a key issue for the safeguarding of our planet is the monitoring of biodiversity. Automated acoustic recognition of species aims to provide a cost-effective method for biodiversity monitoring. This is particularly appealing for detecting endangered animals with a distinctive call, such as the New Forest cicada. To this end, we pursue a crowdsourcing approach, whereby the millions of visitors to the New Forest, where this insect was historically found, will help to monitor its presence by means of a smartphone app that can detect its mating call. Existing research in the field of acoustic insect detection has typically focused upon the classification of recordings collected from fixed field microphones. Such approaches segment a lengthy audio recording into individual segments of insect activity, which are independently classified using cepstral coefficients extracted from the recording as features. This paper reports on a contrasting approach, whereby we use crowdsourcing to collect recordings via a smartphone app, and present an immediate feedback to the users as to whether an insect has been found. Our classification approach does not remove silent parts of the recording via segmentation, but instead uses the temporal patterns throughout each recording to classify the insects present. We show that our approach can successfully discriminate between the call of the New Forest cicada and similar insects found in the New Forest, and is robust to common types of environment noise. A large scale trial deployment of our smartphone app collected over 6000 reports of insect activity from over 1000 users. Despite the cicada not having been rediscovered in the New Forest, the effectiveness of this approach was confirmed for both the detection algorithm, which successfully identified the same cicada through the app in countries where the same species is still present, and of the crowdsourcing methodology, which collected a vast number of recordings and involved thousands of contributors.



近年、計算持続可能性の分野では、人工知能技術を生態学的および環境的問題の解決に応用しようと努めています。生態学において、地球の保全にとって重要な課題の一つは、生物多様性のモニタリングです。種の音響自動認識は、生物多様性モニタリングのための費用対効果の高い方法を提供することを目指しています。これは、ニューフォレストセミのように特徴的な鳴き声を持つ絶滅危惧種の検出に特に有効です。この目的のため、私たちはクラウドソーシングのアプローチを採用しています。このアプローチでは、この昆虫が歴史的に発見されたニューフォレストを訪れる何百万人もの人々が、求愛鳴き声を検出できるスマートフォンアプリを用いて、昆虫の存在を監視することに協力します。音響昆虫検出分野における既存の研究は、一般的に固定フィールドマイクで収集された録音の分類に焦点を当ててきました。このようなアプローチでは、長時間の音声録音を昆虫の活動の個々のセグメントに分割し、録音から抽出されたケプストラム係数を特徴として用いて、各セグメントを個別に分類します。本論文では、対照的なアプローチについて報告します。クラウドソーシングを用いてスマートフォンアプリ経由で録音を収集し、昆虫が発見されたかどうかをユーザーに即座にフィードバックします。この分類アプローチでは、録音の無音部分をセグメンテーションによって削除するのではなく、各録音全体の時間パターンを用いて存在する昆虫を分類します。このアプローチは、ニューフォレストセミの鳴き声とニューフォレストで見られる類似の昆虫を区別でき、一般的な環境ノイズに対しても堅牢であることを示す。このスマートフォンアプリの大規模な試験展開では、1,000人以上のユーザーから6,000件を超える昆虫活動の報告が収集されました。セミはニューフォレストで再発見されなかったものの、このアプローチの有効性は、同じ種がまだ生息する国でアプリを通じて同じセミを識別することに成功した検出アルゴリズムと、膨大な数の録音を収集し数千人の協力者を巻き込んだクラウドソーシング手法の両方で確認されました。

An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information

An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information / 不完全情報を伴うゼロ和拡張形式ゲームのための正確なダブルオラクルアルゴリズム

Developing scalable solution algorithms is one of the central problems in computational game theory. We present an iterative algorithm for computing an exact Nash equilibrium for two-player zero-sum extensive-form games with imperfect information. Our approach combines two key elements: (1) the compact sequence-form representation of extensive-form games and (2) the algorithmic framework of double-oracle methods. The main idea of our algorithm is to restrict the game by allowing the players to play only selected sequences of available actions. After solving the restricted game, new sequences are added by finding best responses to the current solution using fast algorithms. We experimentally evaluate our algorithm on a set of games inspired by patrolling scenarios, board, and card games. The results show significant runtime improvements in games admitting an equilibrium with small support, and substantial improvement in memory use even on games with large support. The improvement in memory use is particularly important because it allows our algorithm to solve much larger game instances than existing linear programming methods. Our main contributions include (1) a generic sequence-form double-oracle algorithm for solving zero-sum extensive-form games; (2) fast methods for maintaining a valid restricted game model when adding new sequences; (3) a search algorithm and pruning methods for computing best-response sequences; (4) theoretical guarantees about the convergence of the algorithm to a Nash equilibrium; (5) experimental analysis of our algorithm on several games, including an approximate version of the algorithm.



スケーラブルなソリューションアルゴリズムの開発は、計算ゲーム理論における中心的な課題の一つです。不完全情報を持つ2人プレイのゼロ和拡張型ゲームの正確なナッシュ均衡を計算する反復アルゴリズムを提示します。このアプローチは、(1)拡張型ゲームのコンパクトなシーケンス形式表現と(2)ダブルオラクル法のアルゴリズムフレームワークという2つの重要な要素を組み合わせたものです。このアルゴリズムの主なアイデアは、プレイヤーが利用可能なアクションの選択されたシーケンスのみを実行できるようにすることで、ゲームを制限することです。制限されたゲームを解いた後、高速アルゴリズムを使用して現在のソリューションに対する最適な応答を見つけることで、新しいシーケンスが追加されます。私たちは、パトロールシナリオ、ボードゲーム、カードゲームに触発された一連のゲームでアルゴリズムを実験的に評価した。結果は、小さなサポートを持つ均衡を許容するゲームで実行時間が大幅に改善され、大きなサポートを持つゲームでもメモリ使用量が大幅に改善されたことを示した。メモリ使用量の改善は、既存の線形計画法よりもはるかに大きなゲームインスタンスをアルゴリズムで解くことができるため、特に重要です。私たちの主な貢献は、(1)ゼロ和拡張型ゲームを解くための汎用的なシーケンス形式ダブルオラクルアルゴリズムです。(2)新しいシーケンスを追加するときに有効な制限ゲームモデルを維持するための高速な方法、(3)最良応答シーケンスを計算するための検索アルゴリズムと剪定方法、(4)アルゴリズムのナッシュ均衡への収束に関する理論的保証、(5)アルゴリズムの近似バージョンを含む、いくつかのゲームでのアルゴリズムの実験的分析。

参考文献

関連情報