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

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

論文

On Overfitting and Asymptotic Bias in Batch Reinforcement Learning with Partial Observability

On Overfitting and Asymptotic Bias in Batch Reinforcement Learning with Partial Observability / 部分観測性を考慮したバッチ強化学習における過学習と漸近的バイアスについて

This paper provides an analysis of the tradeoff between asymptotic bias (suboptimality with unlimited data) and overfitting (additional suboptimality due to limited data) in the context of reinforcement learning with partial observability. Our theoretical analysis formally characterizes that while potentially increasing the asymptotic bias, a smaller state representation decreases the risk of overfitting. This analysis relies on expressing the quality of a state representation by bounding $L_1$ error terms of the associated belief states.  Theoretical results are empirically illustrated when the state representation is a truncated history of observations, both on synthetic POMDPs and on a large-scale POMDP in the context of smartgrids, with real-world data. Finally, similarly to known results in the fully observable setting, we also briefly discuss and empirically illustrate how using function approximators and adapting the discount factor may enhance the tradeoff between asymptotic bias and overfitting in the partially observable context.



本論文では、部分観測可能性を備えた強化学習のコンテキストにおいて、漸近バイアス(無制限のデータによる準最適性)と過学習(限られたデータによる追加の準最適性)のトレードオフを分析します。理論分析では、漸近バイアスが潜在的に増加する一方で、状態表現が小さいほど過学習のリスクが減少することを正式に特徴付けています。この分析は、関連する確信状態の$L_1$誤差項を制限することによって状態表現の品質を表現することに依存しています。理論結果は、状態表現が観測の切り捨てられた履歴である場合に、合成POMDPとスマートグリッドのコンテキストでの大規模POMDPの両方で、実際のデータを使用して経験的に示されています。最後に、完全観測設定における既知の結果と同様に、部分観測コンテキストにおいて関数近似値の使用と割引係数の適応が漸近バイアスと過学習のトレードオフをどのように強化するかについても簡単に議論し、実証的に示します。

Dependency Learning for QBF

Dependency Learning for QBF / QBFのための依存性学習

Quantified Boolean Formulas (QBFs) can be used to succinctly encode problems from domains such as formal verification, planning, and synthesis. One of the main approaches to QBF solving is Quantified Conflict Driven Clause Learning (QCDCL). By default, QCDCL assigns variables in the order of their appearance in the quantifier prefix so as to account for dependencies among variables. Dependency schemes can be used to relax this restriction and exploit independence among variables in certain cases, but only at the cost of nontrivial interferences with the proof system underlying QCDCL. We introduce dependency learning, a new technique for exploiting variable independence within QCDCL that allows solvers to learn variable dependencies on the fly. The resulting version of QCDCL enjoys improved propagation and increased flexibility in choosing variables for branching while retaining ordinary (long-distance) Q-resolution as its underlying proof system. We show that dependency learning can achieve exponential speedups over ordinary QCDCL. Experiments on standard benchmark sets demonstrate the effectiveness of this technique.



量化ブール式（QBF）は、形式検証、計画、合成などの分野の問題を簡潔に符号化するために使用できます。QBFを解く主要なアプローチの1つは、量化衝突駆動節学習（QCDCL）です。QCDCLは、変数間の依存関係を考慮するために、デフォルトで量化子接頭辞に出現する順序で変数を割り当てます。依存関係スキームを使用することで、この制限を緩和し、特定のケースで変数間の独立性を活用することができますが、QCDCLの基盤となる証明システムとの非自明な干渉を犠牲にする必要があります。本稿では、QCDCL内で変数の独立性を活用するための新しい手法である依存関係学習を紹介します。これにより、ソルバーは変数の依存関係をオンザフライで学習できます。結果として得られたQCDCLのバージョンは、通常の（長距離）Q-導出を基礎証明システムとして維持しながら、伝播が改善され、分岐における変数選択の柔軟性が向上しています。依存性学習は、通常のQCDCLと比較して指数関数的な高速化を達成できることを示します。標準的なベンチマークセットを用いた実験により、この手法の有効性が実証されています。

Goal Recognition Design in Deterministic Environments

Goal Recognition Design in Deterministic Environments / 決定論的環境における目標認識設計

Goal recognition design (GRD) facilitates understanding the goals of acting agents through the analysis and redesign of goal recognition models, thus offering a solution for assessing and minimizing the maximal progress of any agent in the model before goal recognition is guaranteed. In a nutshell, given a model of a domain and a set of possible goals, a solution to a GRD problem determines (1) the extent to which actions performed by an agent within the model reveal the agent’s objective; and (2) how best to modify the model so that the objective of an agent can be detected as early as possible. This approach is relevant to any domain in which rapid goal recognition is essential and the model design can be controlled. Applications include intrusion detection, assisted cognition, computer games, and human-robot collaboration. A GRD problem has two components: the analyzed goal recognition setting, and a design model specifying the possible ways the environment in which agents act can be modified so as to facilitate recognition. This work formulates a general framework for GRD in deterministic and partially observable environments, and offers a toolbox of solutions for evaluating and optimizing model quality for various settings. For the purpose of evaluation we suggest the worst case distinctiveness (WCD) measure, which represents the maximal cost of a path an agent may follow before its goal can be inferred by a goal recognition system. We offer novel compilations to classical planning for calculating WCD in settings where agents are bounded-suboptimal. We then suggest methods for minimizing WCD by searching for an optimal redesign strategy within the space of possible modifications, and using pruning to increase efficiency. We support our approach with an empirical evaluation that measures WCD in a variety of GRD settings and tests the efficiency of our compilation-based methods for computing it. We also examine the effectiveness of reducing WCD via redesign and the performance gain brought about by our proposed pruning strategy.



目標認識設計（GRD）は、目標認識モデルの分析と再設計を通じて、行動するエージェントの目標理解を促進し、目標認識が保証される前に、モデル内の任意のエージェントの最大進捗を評価し、最小化するためのソリューションを提供します。簡単に言えば、ドメインモデルと可能な目標の集合が与えられた場合、GRD問題の解決策は、(1)モデル内でエージェントが実行するアクションがエージェントの目標をどの程度明らかにするか、(2)エージェントの目標を可能な限り早期に検出できるようにモデルをどのように修正するのが最適かを決定します。このアプローチは、迅速な目標認識が不可欠であり、モデル設計を制御できるあらゆるドメインに関連しています。応用分野としては、侵入検知、認知支援、コンピュータゲーム、ヒューマンロボットコラボレーションなどがあります。GRD問題は、分析された目標認識設定と、エージェントが行動する環境を認識を促進するために変更できる可能性のある方法を指定する設計モデルの2つの要素で構成されます。本研究では、決定論的かつ部分的に観測可能な環境におけるGRDの一般的な枠組みを定式化し、様々な設定でモデルの品質を評価および最適化するためのソリューションのツールボックスを提供します。評価のために、エージェントが目標認識システムによって目標を推論する前にたどる可能性のある経路の最大コストを表す、最悪ケースの独自性(WCD)尺度を提案します。エージェントが有界準最適である設定でWCDを計算するための、従来の計画に対する新しいコンパイルを提案します。次に、可能な変更の空間内で最適な再設計戦略を探索し、枝刈りを使用して効率を高めることでWCDを最小化する手法を提案します。このアプローチを、様々なGRD設定でWCDを測定し、WCDを計算するためのコンパイルベースの手法の効率をテストする実証的評価で裏付けます。また、再設計によるWCDの削減の有効性と、提案する枝刈り戦略によってもたらされるパフォーマンスの向上についても検証します。

Probabilistic Planning with Reduced Models

Probabilistic Planning with Reduced Models / 縮退モデルを用いた確率的計画

Reduced models are simplified versions of a given domain, designed to accelerate the planning process. Interest in reduced models has grown since the surprising success of determinization in the first international probabilistic planning competition, leading to the development of several enhanced determinization techniques. To address the drawbacks of previous determinization methods, we introduce a family of reduced models in which probabilistic outcomes are classified as one of two types: primary and exceptional. In each model that belongs to this family of reductions, primary outcomes can occur an unbounded number of times per trajectory, while exceptions can occur at most a finite number of times, specified by a parameter. Distinct reduced models are characterized by two parameters: the maximum number of primary outcomes per action, and the maximum number of occurrences of exceptions per trajectory. This family of reductions generalizes the well-known most-likely-outcome determinization approach, which includes one primary outcome per action and zero exceptional outcomes per plan. We present a framework to determine the benefits of planning with reduced models, and develop a continual planning approach that handles situations where the number of exceptions exceeds the specified bound during plan execution. Using this framework, we compare the performance of various reduced models and consider the challenge of generating good ones automatically. We show that each one of the dimensions—allowing more than one primary outcome or planning for some limited number of exceptions—could improve performance relative to standard determinization. The results place previous work on determinization in a broader context and lay the foundation for a systematic exploration of the space of model reductions.



縮小モデルは、計画プロセスを加速するために設計された、特定のドメインの簡略化されたバージョンです。第1回国際確率計画コンペティションにおける決定論的手法の驚くべき成功以来、縮約モデルへの関心が高まり、いくつかの改良型決定論手法が開発されました。従来の決定論的手法の欠点に対処するため、本研究では、確率的結果を主要結果と例外結果の2種類に分類する縮約モデル群を導入します。この縮約モデル群に属する各モデルにおいて、主要結果は軌跡ごとに無制限に発生し、例外結果はパラメータによって指定された有限回数までしか発生しません。異なる縮約モデルは、アクションごとの主要結果の最大数と、軌跡ごとの例外発生の最大回数という2つのパラメータによって特徴付けられます。この縮約モデル群は、アクションごとに主要結果が1つ、プランごとに例外結果が0つという、よく知られた最尤結果決定論アプローチを一般化します。本稿では、縮約モデルを用いたプランニングの利点を判断するためのフレームワークを提示し、プラン実行中に例外の数が指定された上限を超える状況に対応する継続的なプランニングアプローチを開発します。この枠組みを用いて、様々な縮約モデルのパフォーマンスを比較し、優れたモデルを自動生成することの課題について考察します。各次元（複数の主要結果を許容するか、限られた数の例外を計画するか）が、標準的な決定化と比較してパフォーマンスを向上させる可能性があることを示す。この結果は、決定化に関するこれまでの研究をより広い文脈に位置づけ、モデル縮約の空間を体系的に探究するための基盤となります。

Point-Based Value Iteration for Finite-Horizon POMDPs

Point-Based Value Iteration for Finite-Horizon POMDPs / 有限時間区間POMDPのためのポイントベース価値反復法

Partially Observable Markov Decision Processes (POMDPs) are a popular formalism for sequential decision making in partially observable environments. Since solving POMDPs to optimality is a difficult task, point-based value iteration methods are widely used. These methods compute an approximate POMDP solution, and in some cases they even provide guarantees on the solution quality, but these algorithms have been designed for problems with an infinite planning horizon. In this paper we discuss why state-of-the-art point-based algorithms cannot be easily applied to finite-horizon problems that do not include discounting. Subsequently, we present a general point-based value iteration algorithm for finite-horizon problems which provides solutions with guarantees on solution quality. Furthermore, we introduce two heuristics to reduce the number of belief points considered during execution, which lowers the computational requirements. In experiments we demonstrate that the algorithm is an effective method for solving finite-horizon POMDPs.



部分観測マルコフ決定過程（POMDP）は、部分観測環境における逐次意思決定のための一般的な形式主義です。POMDPを最適解にすることは困難な作業であるため、ポイントベースの値反復法が広く用いられています。これらの手法は近似POMDP解を計算し、場合によっては解の品質を保証することさえあるが、これらのアルゴリズムは無限計画期間の問題向けに設計されています。本稿では、最先端のポイントベースアルゴリズムが割引を含まない有限期間問題に容易に適用できない理由について論じる。続いて、有限期間問題に対する、解の品質が保証された解を提供する一般的なポイントベース値反復アルゴリズムを提示します。さらに、実行時に考慮される確信点の数を減らす2つのヒューリスティックを導入し、計算要件を低減します。実験では、このアルゴリズムが有限期間POMDPを解くための効果的な手法であることを実証します。

A Coupled Operational Semantics for Goals and Commitments

A Coupled Operational Semantics for Goals and Commitments / 目標とコミットメントのための結合操作意味論

Commitments capture how an agent relates to another agent, whereas goals describe states of the world that an agent is motivated to bring about.  Commitments are elements of the social state of a set of agents whereas goals are elements of the private states of individual agents.  It makes intuitive sense that goals and commitments are understood as being complementary to each other. More importantly, an agent’s goals and commitments ought to be coherent, in the sense that an agent’s goals would lead it to adopt or modify relevant commitments and an agent’s commitments would lead it to adopt or modify relevant goals.  However, despite the intuitive naturalness of the above connections, they have not been adequately studied in a formal framework. This article provides a combined operational semantics for goals and commitments by relating their respective life cycles as a basis for how these concepts (1) cohere for an individual agent and (2) engender cooperation among agents.  Our semantics yields important desirable properties of convergence of the configurations of cooperating agents, thereby delineating some theoretically well-founded yet practical modes of cooperation in a multiagent system.



コミットメントはエージェントが他のエージェントとどのように関係するかを捉えるのに対し、目標はエージェントがもたらす動機となる世界の状態を記述します。コミットメントはエージェント集合の社会的状態の要素であるのに対し、目標は個々のエージェントの私的状態の要素です。目標とコミットメントが互いに補完的であると理解されることは直感的に理解できます。さらに重要なのは、エージェントの目標とコミットメントは、エージェントの目標が関連するコミットメントを採用または修正するように導き、エージェントのコミットメントが関連する目標を採用または修正するように導くという意味で、首尾一貫している必要があることです。しかし、上記のつながりは直感的に自然であるにもかかわらず、正式な枠組みの中で十分に研究されていません。この記事では、目標とコミットメントのそれぞれのライフサイクルを関連付けることで、これらの概念が(1)個々のエージェントにとって首尾一貫しており、(2)エージェント間の協力を生み出す方法の基礎として、目標とコミットメントの操作的意味論を組み合わせて提供します。我々のセマンティクスは、協力するエージェントの構成の収束に関する重要な望ましい特性をもたらし、それによってマルチエージェントシステムにおける理論的に十分に根拠のある実用的な協力モードのいくつかを描き出します。

Strong Stubborn Set Pruning for Star-Topology Decoupled State Space Search

Strong Stubborn Set Pruning for Star-Topology Decoupled State Space Search / スタートポロジ分離状態空間探索のための強力な頑固集合枝刈り

Analyzing reachability in large discrete transition systems is an important sub-problem in several areas of AI, and of CS in general. State space search is a basic method for conducting such an analysis. A wealth of techniques have been proposed to reduce the search space without affecting the existence of (optimal) solution paths. In particular, strong stubborn set (SSS) pruning is a prominent such method, analyzing action dependencies to prune commutative parts of the search space. We herein show how to apply this idea to star-topology decoupled state space search, a recent search reformulation method invented in the context of classical AI planning.Star-topology decoupled state space search, short decoupled search, addresses planning tasks where a single center component interacts with several leaf components. The search exploits a form of conditional independence arising in this setting: given a fixed path p of transitions by the center, the possible leaf moves compliant with p are independent across the leaves. Decoupled search thus searches over center paths only, maintaining the compliant paths for each leaf separately. This avoids the enumeration of combined states across leaves.Just like standard search, decoupled search is adversely affected by commutative parts of its search space. The adaptation of strong stubborn set pruning is challenging due to the more complex structure of the search space, and the resulting ways in which action dependencies may affect the search. We spell out how to address this challenge, designing optimality-preserving decoupled strong stubborn set (DSSS) pruning methods. We introduce a design for star topologies in full generality, as well as simpler design variants for the practically relevant fork and inverted fork special cases. We show that there are cases where DSSS pruning is exponentially more effective than both, decoupled search and SSS pruning, exhibiting true synergy where the whole is more than the sum of its parts. Empirically, DSSS pruning reliably inherits the best of its components, and sometimes outperforms both.



大規模な離散遷移システムにおける到達可能性の解析は、AI、そして一般的にはコンピュータサイエンスのいくつかの分野における重要な部分問題です。状態空間探索は、このような解析を行うための基本的な手法です。（最適な）解パスの存在に影響を与えずに探索空間を縮小するための多くの手法が提案されています。特に、強力な頑固な集合（SSS）の枝刈りは、そのような手法として広く知られており、アクションの依存関係を解析して探索空間の可換部分を枝刈りします。ここでは、この考え方を、古典的なAIプランニングの文脈で発明された最近の探索再定式化手法であるスタートポロジ分離状態空間探索に適用する方法を示します。スタートポロジ分離状態空間探索（略して分離探索）は、単一の中心コンポーネントが複数の葉コンポーネントと相互作用するプランニングタスクに対処します。探索は、この設定で発生する条件付き独立性の形式を利用します。中心による遷移の固定パスpが与えられた場合、pに準拠する可能なリーフの移動はリーフ全体で独立しています。したがって、分離探索は中心のパスのみを探索し、各リーフの準拠パスを個別に維持します。これにより、リーフ全体にわたる結合状態の列挙を回避します。標準の探索と同様に、分離探索は探索空間の可換部分によって悪影響を受けます。強力な頑固な集合の剪定の適応は、探索空間の構造が複雑になり、その結果アクションの依存関係が探索に影響を与える可能性があるため、困難です。この課題に対処する方法を説明し、最適性を維持する分離強力頑固な集合(DSSS)の剪定手法を設計します。完全な一般性を備えたスター トポロジの設計と、実際に関連するフォークおよび逆フォークの特殊なケースに対するより単純な設計バリアントを紹介します。DSSSプルーニングが、分離探索とSSSプルーニングの両方よりも指数関数的に効果的であるケースがあり、全体が部分の総和を上回る真の相乗効果を発揮することを示します。経験的に、DSSSプルーニングは各構成要素の最良の部分を確実に継承し、場合によっては両方を上回る性能を発揮します。

Weighted Matching Markets with Budget Constraints

Weighted Matching Markets with Budget Constraints / 予算制約付き重み付きマッチング市場

We investigate markets with a set of students on one side and a set of colleges on the other. A student and college can be linked by a weighted contract that defines the student’s wage, while a college’s budget for hiring students is limited. Stability is a crucial requirement for matching mechanisms to be applied in the real world. A standard stability requirement is coalitional stability, i.e., no pair of a college and group of students has any incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is coNP-complete, and the problem of finding whether a coalitionally stable matching exists in a given market, is SigmaP2-complete: NPNP-complete. Other negative results also hold when blocking coalitions contain at most two students and one college. Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, where no pair of a college and single student has an incentive to deviate. Unfortunately, a pairwise stable matching is not guaranteed to exist either. Thus, we consider a restricted market called a typed weighted market, in which students are partitioned into types that induce their possible wages. We then design a strategy-proof and Pareto efficient mechanism that works in polynomial-time for computing a pairwise stable matching in typed weighted markets.



我々は、一方に学生の集合、もう一方に大学の集合が存在する市場を調査します。学生と大学は、学生の賃金を規定する加重契約によって結び付けられるが、大学の学生採用予算は限られています。現実世界でマッチングメカニズムを適用するには、安定性が極めて重要な要件となります。標準的な安定性要件は、連合安定性、すなわち、大学と学生グループのいずれのペアにも、逸脱するインセンティブが存在しないことです。我々は、連合的に安定したマッチングが存在することが保証されていないことを発見した。与えられたマッチングにおける連合安定性の検証はcoNP完全であり、与えられた市場において連合的に安定したマッチングが存在するかどうかを判定する問題はSigmaP2完全：NPNP完全です。ブロッキング連合が最大で2人の学生と1つの大学を含む場合、他の否定的な結果も成立します。これらの計算困難性の結果を踏まえ、我々は、大学と1人の学生のいずれのペアにも逸脱するインセンティブが存在しない、ペアワイズ安定性と呼ばれるより弱い安定性要件を追求します。残念ながら、ペアワイズ安定マッチングも存在することが保証されていない。そこで我々は、型付き加重市場と呼ばれる制限付き市場を考察します。この市場では、学生はそれぞれの賃金を誘導するタイプに分割されます。そして、型付き加重市場におけるペアワイズ安定マッチングを多項式時間で計算するための、戦略証明とパレート効率的なメカニズムを設計します。

OptStream: Releasing Time Series Privately

OptStream: Releasing Time Series Privately / OptStream: 時系列の非公開リリース

Many applications of machine learning and optimization operate on data streams. While these datasets are fundamental to fuel decision-making algorithms, often they contain sensitive information about individuals, and their usage poses significant privacy risks. Motivated by an application in energy systems, this paper presents OptStream, a novel algorithm for releasing differentially private data streams under the w-event model of privacy. OptStream is a 4-step procedure consisting of sampling, perturbation, reconstruction, and post-processing modules. First, the sampling module selects a small set of points to access in each period of interest. Then, the perturbation module adds noise to the sampled data points to guarantee privacy. Next, the reconstruction module re-assembles non-sampled data points from the perturbed sample points. Finally, the post-processing module uses convex optimization over the privacy-preserving output of the previous modules, as well as the privacy-preserving answers of additional queries on the data stream, to improve accuracy by redistributing the added noise. OptStream is evaluated on a test case involving the release of a real data stream from the largest European transmission operator. Experimental results show that OptStream may not only improve the accuracy of state-of-the-art methods by at least one order of magnitude but also supports accurate load forecasting on the privacy-preserving data.



機械学習と最適化の多くのアプリケーションは、データストリームをベースとしています。これらのデータセットは意思決定アルゴリズムの基盤となるが、個人に関する機密情報を含むことが多く、その使用は重大なプライバシーリスクをもたらす。エネルギーシステムへの応用を契機として、本論文では、wイベントプライバシーモデルに基づき、差分プライバシーデータストリームを解放するための新しいアルゴリズム、OptStreamを紹介します。OptStreamは、サンプリング、摂動、再構成、および後処理モジュールからなる4段階の手順です。まず、サンプリングモジュールは、各対象期間においてアクセスする少数のポイントセットを選択します。次に、摂動モジュールは、プライバシーを保証するために、サンプリングされたデータポイントにノイズを追加します。次に、再構成モジュールは、摂動されたサンプルポイントから、サンプリングされていないデータポイントを再構成します。最後に、後処理モジュールは、以前のモジュールのプライバシー保護出力と、データストリームに対する追加クエリのプライバシー保護応答に対して凸最適化を適用し、追加されたノイズを再分配することで精度を向上させます。OptStreamは、ヨーロッパ最大の伝送事業者からの実際のデータストリームを流すテストケースで評価されました。実験結果によると、OptStreamは最先端の手法の精度を少なくとも1桁向上させるだけでなく、プライバシー保護データにおける正確な負荷予測もサポートします。

IKBT: Solving Symbolic Inverse Kinematics with Behavior Tree

IKBT: Solving Symbolic Inverse Kinematics with Behavior Tree / IKBT: 行動木を用いた記号逆運動学の解法

Inverse kinematics solves the problem of how to control robot arm joints to achieve desired end effector positions, which is critical to any robot arm design and implementations of control algorithms. It is a common misunderstanding that closed-form inverse kinematics analysis is solved. Popular software and algorithms, such as gradient descent or any multi-variant equations solving algorithm, claims solving inverse kinematics but only on the numerical level. While the numerical inverse kinematics solutions are relatively straightforward to obtain, these methods often fail, due to dependency on specific numerical values, even when the inverse kinematics solutions exist. Therefore, closed-form inverse kinematics analysis is superior, but there is no generalized automated algorithm. Up till now, the high-level logical reasoning involved in solving closed-form inverse kinematics made it hard to automate, so it’s handled by human experts. We developed IKBT, a knowledge-based intelligent system that can mimic human experts’ behaviors in solving closed-from inverse kinematics using Behavior Tree. Knowledge and rules used by engineers when solving closed-from inverse kinematics are encoded as actions in Behavior Tree. The order of applying these rules is governed by higher level composite nodes, which resembles the logical reasoning process of engineers. It is also the first time that the dependency of joint variables, an important issue in inverse kinematics analysis, is automatically tracked in graph form. Besides generating closed-form solutions, IKBT also explains its solving strategies in human (engineers) interpretable form. This is a proof-of-concept of using Behavior Trees to solve high-cognitive problems.



逆運動学は、ロボットアームの関節を制御してエンドエフェクタの望ましい位置を達成する方法という問題を解決します。これは、あらゆるロボットアームの設計と制御アルゴリズムの実装にとって重要です。閉形式の逆運動学解析は解決されているというのがよくある誤解です。勾配降下法や多変数方程式を解くアルゴリズムなどの人気のソフトウェアやアルゴリズムは、逆運動学を解くと主張していますが、それは数値レベルのみです。数値逆運動学解は比較的簡単に取得できますが、逆運動学解が存在する場合でも、特定の数値に依存しているため、これらの方法は失敗することがよくあります。したがって、閉形式の逆運動学解析は優れていますが、一般化された自動化アルゴリズムはありません。これまで、閉形式の逆運動学を解くには高度な論理的推論が必要であり、自動化が困難であったため、人間の専門家によって処理されていました。我々は、ビヘイビアツリーを用いて閉形式逆運動学を解く際の人間の専門家の行動を模倣できる知識ベース知能システムIKBTを開発しました。エンジニアが閉形式逆運動学を解く際に用いる知識とルールは、ビヘイビアツリーのアクションとしてコード化されています。これらのルールを適用する順序は、エンジニアの論理的推論プロセスに似た高レベルの複合ノードによって制御されます。また、逆運動学解析において重要な問題である関節変数の依存関係がグラフ形式で自動的に追跡されるのは、今回が初めてです。閉形式解を生成するだけでなく、IKBTは人間（エンジニア）が解釈可能な形式で解法戦略を説明します。これは、ビヘイビアツリーを用いて高度な認知的問題を解決するという概念実証です。

Unifying System Health Management and Automated Decision Making

Unifying System Health Management and Automated Decision Making / システムヘルス管理と自動意思決定の統合

Health management of complex dynamic systems has evolved from simple automated alarms into a subfield of artificial intelligence with techniques for analyzing off-nominal conditions and generating responses. This evolution took place largely apart from the development of automated system control, planning, and scheduling (generally referred to in this work as decision making). While there have been efforts to establish an information exchange between system health management and decision making, successful practical implementations of integrated architectures remain limited. This article proposes that rather than being treated as connected yet distinct entities, system health management and decision making should be unified in their formulations. Enabled by advances in modeling and algorithms, we believe that a unified approach will increase systems’ resilience to faults and improve their effectiveness. We overview the prevalent system health management methodology, illustrate its limitations through numerical examples, and describe a proposed unified approach. We then show how typical system health management concepts are accommodated in the proposed approach without loss of functionality or generality. A computational complexity analysis of the unified approach is also provided.



複雑な動的システムの健全性管理は、単純な自動アラームから、異常状態を分析して応答を生成する技術を備えた人工知能のサブフィールドへと進化しました。この進化は、自動化されたシステム制御、計画、およびスケジューリング（この研究では一般に意思決定と呼ぶ）の開発とは別に、主に起こりました。システム健全性管理と意思決定の間で情報交換を確立する取り組みは行われてきましたが、統合アーキテクチャの成功した実用的な実装は限られています。この記事では、システム健全性管理と意思決定を、関連しながらも別々のエンティティとして扱うのではなく、定式化において統一することを提案します。モデリングとアルゴリズムの進歩により、統一されたアプローチはシステムの障害に対する回復力を高め、有効性を改善すると考えています。一般的なシステム健全性管理方法論を概観し、数値例でその限界を示し、提案された統一アプローチについて説明します。次に、一般的なシステム健全性管理の概念が、機能性や一般性を損なうことなく、提案されたアプローチにどのように組み込まれているかを示します。統一アプローチの計算複雑性分析も提供します。

Autonomous Target Search with Multiple Coordinated UAVs

Autonomous Target Search with Multiple Coordinated UAVs / 複数の協調UAVによる自律ターゲット探索

Search and tracking is the problem of locating a moving target and following it to its destination. In this work, we consider a scenario in which the target moves across a large geographical area by following a road network and the search is performed by a team of unmanned aerial vehicles (UAVs). We formulate search and tracking as a combinatorial optimization problem and prove that the objective function is submodular. We exploit this property to devise a greedy algorithm. Although this algorithm does not offer strong theoretical guarantees because of the presence of temporal constraints that limit the feasibility of the solutions, it presents remarkably good performance, especially when several UAVs are available for the mission. As the greedy algorithm suffers when resources are scarce, we investigate two alternative optimization techniques: Constraint Programming (CP) and AI planning. Both approaches struggle to cope with large problems, and so we strengthen them by leveraging the greedy algorithm. We use the greedy solution to warm start the CP model and to devise a domain-dependent heuristic for planning. Our extensive experimental evaluation studies the scalability of the different techniques and identifies the conditions under which one approach becomes preferable to the others.



探索と追跡は、移動するターゲットを見つけて目的地まで追跡する問題です。本研究では、目標が道路網に沿って広大な地理的領域を移動し、無人航空機（UAV）のチームによって捜索が行われるシナリオを検討します。捜索と追跡を組合せ最適化問題として定式化し、目的関数が劣モジュラであることを証明します。この性質を利用して貪欲アルゴリズムを考案します。このアルゴリズムは、解の実現可能性を制限する時間的制約が存在するため、強力な理論的保証は提供できないものの、特に複数のUAVがミッションに利用可能な場合、非常に優れた性能を示す。貪欲アルゴリズムはリソースが不足している状況では性能が低下するため、制約プログラミング（CP）とAIプランニングという2つの代替最適化手法を検討します。どちらの手法も大規模な問題への対応が困難であるため、貪欲アルゴリズムを活用することでこれらの手法を強化します。貪欲解を用いてCPモデルのウォームスタートを行い、プランニングのためのドメイン依存ヒューリスティックを考案します。広範な実験評価により、各手法のスケーラビリティを調査し、ある手法が他の手法よりも優れている条件を特定します。

A Survey of Cross-lingual Word Embedding Models

A Survey of Cross-lingual Word Embedding Models / クロスリンガル単語埋め込みモデルのサーベイ

Cross-lingual representations of words enable us to reason about word meaning in multilingual contexts and are a key facilitator of cross-lingual transfer when developing natural language processing models for low-resource languages. In this survey, we provide a comprehensive typology of cross-lingual word embedding models. We compare their data requirements and objective functions. The recurring theme of the survey is that many of the models presented in the literature optimize for the same objectives, and that seemingly different models are often equivalent, modulo optimization strategies, hyper-parameters, and such. We also discuss the different ways cross-lingual word embeddings are evaluated, as well as future challenges and research horizons.



単語のクロスリンガル表現は、多言語文脈における単語の意味の推論を可能にし、リソースの少ない言語向けの自然言語処理モデルを開発する際に、クロスリンガル転送を促進する重要な要素となります。本調査では、クロスリンガル単語埋め込みモデルの包括的な類型を提示します。また、それらのデータ要件と目的関数を比較します。本調査で繰り返し取り上げられるテーマは、文献で提示されているモデルの多くが同じ目的を最適化しており、一見異なるモデルであっても、最適化戦略やハイパーパラメータなどを除けば、多くの場合同等であるということです。また、クロスリンガル単語埋め込みの様々な評価方法、そして今後の課題と研究の展望についても考察します。

Computing Multi-Modal Journey Plans under Uncertainty

Computing Multi-Modal Journey Plans under Uncertainty / 不確実性下におけるマルチモーダル旅程計画の計算

Multi-modal journey planning, which allows multiple types of transport within a single trip, is becoming increasingly popular, due to a strong practical interest and an increasing availability of data. In real life, transport networks feature uncertainty. Yet, most approaches assume a deterministic environment, making plans more prone to failures such as missed connections and major delays in the arrival.This paper presents an approach to computing optimal contingent plans in multi-modal journey planning. The problem is modeled as a search in an and/or state space. We describe search enhancements used on top of the AO* algorithm. Enhancements include admissible heuristics, multiple types of pruning that preserve the completeness and the optimality, and a hybrid search approach with a deterministic and a nondeterministic search. We demonstrate an NP-hardness result, with the hardness stemming from the dynamically changing distributions of the travel time random variables. We perform a detailed empirical analysis on realistic transport networks from cities such as Montpellier, Rome and Dublin. The results demonstrate the effectiveness of our algorithmic contributions, and the benefits of contingent plans as compared to standard sequential plans, when the arrival and departure times of buses are characterized by uncertainty.



単一の移動で複数の交通手段を利用できるマルチモーダル旅程計画は、実用性への強い関心とデータの入手可能性の向上により、ますます普及しつつあります。現実の交通網は不確実性を備えています。しかし、ほとんどのアプローチは決定論的な環境を前提としているため、乗り継ぎの遅延や到着の大幅な遅延といった計画の失敗が発生しやすくなります。本論文では、マルチモーダル旅程計画における最適なコンティンジェントプランを計算するアプローチを提示します。この問題は、and/or状態空間における探索としてモデル化されます。AO*アルゴリズムに加えられる探索強化について説明します。強化には、許容ヒューリスティック、完全性と最適性を維持する複数種類の枝刈り、そして決定論的探索と非決定論的探索を組み合わせたハイブリッド探索アプローチが含まれます。NP困難性を示す結果を示し、その困難性は移動時間確率変数の分布が動的に変化することに起因するとしています。モンペリエ、ローマ、ダブリンなどの都市の現実的な交通網を対象に、詳細な実証分析を行います。結果は、バスの到着時刻と出発時刻が不確実である場合に、我々のアルゴリズムの貢献の有効性と、標準的な逐次計画と比較したコンティンジェント計画の利点を実証しています。

Automatic Language Identification in Texts: A Survey

Automatic Language Identification in Texts: A Survey / テキストにおける自動言語識別：サーベイ

Language identification (“LI”) is the problem of determining the natural language that a document or part thereof is written in. Automatic LI has been extensively researched for over fifty years. Today, LI is a key part of many text processing pipelines, as text processing techniques generally assume that the language of the input text is known. Research in this area has recently been especially active. This article provides a brief history of LI research, and an extensive survey of the features and methods used in the LI literature. We describe the features and methods using a unified notation, to make the relationships between methods clearer. We discuss evaluation methods, applications of LI, as well as off-the-shelfLI systems that do not require training by the end user. Finally, we identify open issues, survey the work to date on each issue, and propose future directions for research in LI.



言語識別（LI）とは、文書またはその一部がどの自然言語で書かれているかを判断する問題です。自動LIは50年以上にわたって広く研究されてきました。今日、テキスト処理技術は一般的に入力テキストの言語が既知であると想定しているため、LIは多くのテキスト処理パイプラインの重要な部分となっています。この分野の研究は近年特に活発化しています。本稿では、LI研究の簡単な歴史と、LI関連の文献で使用されている機能と手法の広範な調査を提供します。手法間の関係を明確にするために、統一された表記法を用いて機能と手法を説明します。LIの評価方法、応用、そしてエンドユーザーによるトレーニングを必要としない既製のLIシステムについて説明します。最後に、未解決の課題を特定し、各課題に関するこれまでの研究を調査し、LI研究の将来の方向性を提案します。

The Mathematics of Changing One’s Mind, via Jeffrey’s or via Pearl’s Update Rule

The Mathematics of Changing One’s Mind, via Jeffrey’s or via Pearl’s Update Rule / Jeffreyの更新則またはPearlの更新則による考えを変える数学

Evidence in probabilistic reasoning may be ‘hard’ or ‘soft’, that is, it may be of yes/no form, or it may involve a strength of belief, in the unit interval [0, 1]. Reasoning with soft, [0, 1]-valued evidence is important in many situations but may lead to different, confusing interpretations. This paper intends to bring more mathematical and conceptual clarity to the field by shifting the existing focus from specification of soft evidence to accomodation of soft evidence. There are two main approaches, known as Jeffrey’s rule and Pearl’s method; they give different outcomes on soft evidence. This paper argues that they can be understood as correction and as improvement. It describes these two approaches as different ways of updating with soft evidence, highlighting their differences, similarities and applications. This account is based on a novel channel-based approach to Bayesian probability. Proper understanding of these two update mechanisms is highly relevant for inference, decision tools and probabilistic programming languages.



確率推論における証拠は、「ハード」または「ソフト」です。つまり、はい/いいえ形式の場合もあれば、単位区間[0, 1]における信念の強さを伴う場合もあります。[0, 1]値のソフトな証拠を用いた推論は多くの状況で重要であるが、異なる解釈や混乱を招く可能性があります。本論文は、既存の焦点をソフトな証拠の特定からソフトな証拠の適応へと移すことで、この分野に数学的および概念的な明確さをもたらすことを目指す。ジェフリーの法則とパール法として知られる2つの主要なアプローチがあり、これらはソフトな証拠に対して異なる結果をもたらす。本論文では、これらを修正法と改善法として理解できると主張します。本論文では、これら2つのアプローチをソフトな証拠を用いた更新の異なる方法として説明し、その相違点、類似点、そして応用例を強調します。この説明は、ベイズ確率に対する新しいチャネルベースのアプローチに基づいています。これら2つの更新メカニズムを適切に理解することは、推論、意思決定ツール、そして確率的プログラミング言語にとって非常に重要です。

REBA: A Refinement-Based Architecture for Knowledge Representation and Reasoning in Robotics

REBA: A Refinement-Based Architecture for Knowledge Representation and Reasoning in Robotics / REBA: ロボティクスにおける知識表現と推論のための洗練に基づくアーキテクチャ

This article describes REBA, a knowledge representation and reasoning architecture for robots that is based on tightly-coupled transition diagrams of the domain at two different levels of granularity. An action language is extended to support non-boolean fluents and non-deterministic causal laws, and used to describe the domain’s transition diagrams, with the fine-resolution transition diagram being defined as a refinement of the coarse-resolution transition diagram. The coarse-resolution system description, and a history that includes prioritized defaults, are translated into an Answer Set Prolog (ASP) program. For any given goal, inference in the ASP program provides a plan of abstract actions. To implement each such abstract action, the robot automatically zooms to the part of the fine-resolution transition diagram relevant to this action. The zoomed fine-resolution system description, and a probabilistic representation of the uncertainty in sensing and actuation, are used to construct a partially observable Markov decision process (POMDP). The policy obtained by solving the POMDP is invoked repeatedly to implement the abstract action as a sequence of concrete actions. The fine-resolution outcomes of executing these concrete actions are used to infer coarse-resolution outcomes that are added to the coarse-resolution history and used for subsequent coarse-resolution reasoning. The architecture thus combines the complementary strengths of declarative programming and probabilistic graphical models to represent and reason with non-monotonic logic-based and probabilistic descriptions of uncertainty and incomplete domain knowledge. In addition, we describe a general methodology for the design of software components of a robot based on these knowledge representation and reasoning tools, and provide a path for proving the correctness of these components. The architecture is evaluated in simulation and on a mobile robot finding and moving target objects to desired locations in indoor domains, to show that the architecture supports reliable and efficient reasoning with violation of defaults, noisy observations and unreliable actions, in complex domains.



本稿では、ロボットのための知識表現および推論アーキテクチャであるREBAについて述べる。REBAは、2つの異なる粒度レベルでドメインの密結合遷移図に基づく。アクション言語は、非ブール型流暢性と非決定論的因果律をサポートするように拡張され、ドメインの遷移図を記述するために使用されます。高分解能遷移図は、粗分解能遷移図の改良として定義されます。粗分解能システム記述と、優先順位付けされたデフォルトを含む履歴は、Answer Set Prolog (ASP)プログラムに変換されます。与えられた目標に対して、ASPプログラムの推論は抽象的なアクションの計画を提供します。ロボットは、このような抽象的なアクションをそれぞれ実行するために、高分解能遷移図の該当部分に自動的にズームインします。ズームインされた高分解能システム記述と、センシングおよびアクチュエーションにおける不確実性の確率的表現は、部分観測マルコフ決定過程(POMDP)の構築に使用されます。POMDPを解くことで得られるポリシーは、抽象アクションを具体的なアクションのシーケンスとして実装するために繰り返し呼び出されます。これらの具体的なアクションの実行による高分解能の結果は、粗分解能の結果を推論するために用いられます。これらの結果は粗分解能の履歴に追加され、後続の粗分解能の推論に用いられます。このように、このアーキテクチャは、宣言的プログラミングと確率的グラフィカルモデルの相補的な強みを組み合わせることで、不確実性と不完全なドメイン知識を非単調な論理ベースおよび確率的記述によって表現し、推論します。さらに、これらの知識表現および推論ツールに基づいてロボットのソフトウェアコンポーネントを設計するための一般的な方法論を説明し、これらのコンポーネントの正しさを証明するためのパスを提供します。このアーキテクチャは、シミュレーションと、屋内領域でターゲットオブジェクトを検出して目的の場所に移動させる移動ロボット上で評価され、複雑なドメインにおいて、デフォルト違反、ノイズの多い観測、および信頼できないアクションを伴う信頼性の高い効率的な推論をサポートすることを示します。

参考文献

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

関連情報

• Journal of Artificial Intelligence Research: 論文一覧