Location-Based Reasoning about Complex Multi-Agent Behavior
複雑なマルチエージェント行動に関する位置ベース推論
Recent research has shown that surprisingly rich models of human activity can be learned from GPS (positional) data. However, most effort to date has concentrated on modeling single individuals or statistical properties of groups of people. Moreover, prior work focused solely on modeling actual successful executions (and not failed or attempted executions) of the activities of interest. We, in contrast, take on the task of understanding human interactions, attempted interactions, and intentions from noisy sensor data in a fully relational multi-agent setting. We use a real-world game of capture the flag to illustrate our approach in a well-defined domain that involves many distinct cooperative and competitive joint activities. We model the domain using Markov logic, a statistical-relational language, and learn a theory that jointly denoises the data and infers occurrences of high-level activities, such as a player capturing an enemy. Our unified model combines constraints imposed by the geometry of the game area, the motion model of the players, and by the rules and dynamics of the game in a probabilistically and logically sound fashion. We show that while it may be impossible to directly detect a multi-agent activity due to sensor noise or malfunction, the occurrence of the activity can still be inferred by considering both its impact on the future behaviors of the people involved as well as the events that could have preceded it. Further, we show that given a model of successfully performed multi-agent activities, along with a set of examples of failed attempts at the same activities, our system automatically learns an augmented model that is capable of recognizing success and failure, as well as goals of people’s actions with high accuracy. We compare our approach with other alternatives and show that our unified model, which takes into account not only relationships among individual players, but also relationships among activities over the entire length of a game, although more computationally costly, is significantly more accurate. Finally, we demonstrate that explicitly modeling unsuccessful attempts boosts performance on other important recognition tasks.
近年の研究では、GPS（位置情報）データから驚くほど豊富な人間活動モデルを学習できることが示されています。しかし、これまでの研究のほとんどは、個人や集団の統計的特性をモデル化することに集中していました。さらに、先行研究は、関心活動の実際の成功例（失敗例や試行例ではない）のモデル化のみに焦点を当てていました。これに対し、私たちは、ノイズの多いセンサーデータから、完全に関係的なマルチエージェント環境における人間の相互作用、試行された相互作用、そして意図を理解するという課題に取り組みます。私たちは、多くの異なる協力的および競争的な共同活動を含む明確に定義された領域において、現実世界の旗取りゲームを用いて私たちのアプローチを説明します。私たちは、統計的関係言語であるマルコフ論理を用いてこの領域をモデル化し、データのノイズ除去と、プレイヤーが敵を捕獲するなどの高レベルな活動の発生を推論する理論を学習します。私たちの統一モデルは、ゲームエリアの形状、プレイヤーの運動モデル、そしてゲームのルールとダイナミクスによって課される制約を、確率的かつ論理的に健全な方法で組み合わせます。センサーノイズや故障によりマルチエージェント活動を直接検出できない場合でも、関係者の将来の行動への影響と、その前に発生した可能性のあるイベントの両方を考慮することで、活動の発生を推測できることを示します。さらに、成功したマルチエージェント活動のモデルと、同じ活動における失敗した試行の例のセットが与えられた場合、システムは成功と失敗、そして人々の行動の目的を高精度で認識できる拡張モデルを自動的に学習することを示します。このアプローチを他の代替アプローチと比較し、個々のプレーヤー間の関係だけでなく、ゲーム全体にわたる活動間の関係も考慮する統合モデルは、計算コストは高くなりますが、はるかに正確であることを示します。最後に、失敗した試みを明示的にモデル化することで、他の重要な認識タスクのパフォーマンスが向上することを実証します。
Learning to Win by Reading Manuals in a Monte-Carlo Framework
モンテカルロフレームワークにおけるマニュアルを読むことで勝つための学習
Domain knowledge is crucial for effective performance in autonomous control systems. Typically, human effort is required to encode this knowledge into a control algorithm. In this paper, we present an approach to language grounding which automatically interprets text in the context of a complex control application, such as a game, and uses domain knowledge extracted from the text to improve control performance. Both text analysis and control strategies are learned jointly using only a feedback signal inherent to the application. To effectively leverage textual information, our method automatically extracts the text segment most relevant to the current game state, and labels it with a task-centric predicate structure. This labeled text is then used to bias an action selection policy for the game, guiding it towards promising regions of the action space. We encode our model for text analysis and game playing in a multi-layer neural network, representing linguistic decisions via latent variables in the hidden layers, and game action quality via the output layer. Operating within the Monte-Carlo Search framework, we estimate model parameters using feedback from simulated games. We apply our approach to the complex strategy game Civilization II using the official game manual as the text guide. Our results show that a linguistically-informed game-playing agent significantly outperforms its language-unaware counterpart, yielding a 34% absolute improvement and winning over 65% of games when playing against the built-in AI of Civilization.
自律制御システムの効果的なパフォーマンスには、ドメイン知識が不可欠です。通常、この知識を制御アルゴリズムにエンコードするには人間の労力が必要です。本論文では、ゲームなどの複雑な制御アプリケーションのコンテキストにおいてテキストを自動的に解釈し、テキストから抽出したドメイン知識を用いて制御性能を向上させる言語グラウンディングの手法を提示します。テキスト分析と制御戦略は、アプリケーション固有のフィードバック信号のみを用いて共同学習されます。テキスト情報を効果的に活用するために、本手法は、現在のゲーム状態に最も関連性の高いテキストセグメントを自動的に抽出し、タスク中心の述語構造でラベル付けします。このラベル付けされたテキストは、ゲームの行動選択方針をバイアスし、行動空間の有望な領域へと導くために用いられます。テキスト分析とゲームプレイのための本モデルは、多層ニューラルネットワークに符号化され、隠れ層の潜在変数を介して言語的決定を、出力層を介してゲーム行動の質を表現します。モンテカルロ探索フレームワーク内で動作させ、シミュレーションゲームからのフィードバックを用いてモデルパラメータを推定します。本手法は、公式ゲームマニュアルをテキストガイドとして用い、複雑戦略ゲーム「Civilization II」に適用します。私たちの結果では、言語情報を備えたゲーム プレイ エージェントは、言語を認識しないエージェントよりも大幅にパフォーマンスが優れており、Civilizationの組み込みAIと対戦すると、絶対値が34%向上し、ゲームの65%以上で勝利することがわかりました。
A Market-Inspired Approach for Intersection Management in Urban Road Traffic Networks
都市道路交通網における交差点管理のための市場指向アプローチ
Traffic congestion in urban road networks is a costly problem that affects all major cities in developed countries. To tackle this problem, it is possible (i) to act on the supply side, increasing the number of roads or lanes in a network, (ii) to reduce the demand, restricting the access to urban areas at specific hours or to specific vehicles, or (iii) to improve the efficiency of the existing network, by means of a widespread use of so-called Intelligent Transportation Systems (ITS). In line with the recent advances in smart transportation management infrastructures, ITS has turned out to be a promising field of application for artificial intelligence techniques. In particular, multiagent systems seem to be the ideal candidates for the design and implementation of ITS. In fact, drivers can be naturally modelled as autonomous agents that interact with the transportation management infrastructure, thereby generating a large-scale, open, agent-based system. To regulate such a system and maintain a smooth and efficient flow of traffic, decentralised mechanisms for the management of the transportation infrastructure are needed.In this article we propose a distributed, market-inspired, mechanism for the management of a future urban road network, where intelligent autonomous vehicles, operated by software agents on behalf of their human owners, interact with the infrastructure in order to travel safely and efficiently through the road network. Building on the reservation-based intersection control model proposed by Dresner and Stone, we consider two different scenarios: one with a single intersection and one with a network of intersections. In the former, we analyse the performance of a novel policy based on combinatorial auctions for the allocation of reservations. In the latter, we analyse the impact that a traffic assignment strategy inspired by competitive markets has on the drivers’ route choices. Finally we propose an adaptive management mechanism that integrates the auction-based traffic control policy with the competitive traffic assignment strategy.
都市道路網における交通渋滞は、先進国の主要都市すべてに影響を与えるコストのかかる問題です。この問題に対処するには、(i)供給側に働きかけてネットワーク内の道路や車線の数を増やす、(ii)需要を減らして特定の時間帯や特定の車両に都市部へのアクセスを制限する、(iii)いわゆる高度道路交通システム(ITS)を広く利用して既存のネットワークの効率を改善するといったことが考えられます。近年のスマート交通管理インフラの進歩に伴い、ITSは人工知能技術の有望な応用分野であることが判明しています。特に、マルチエージェントシステムはITSの設計と実装に最適な候補と思われます。実際、ドライバーは交通管理インフラと対話する自律エージェントとして自然にモデル化することができ、それによって大規模でオープンなエージェントベースシステムを生成できます。このようなシステムを調整し、円滑で効率的な交通の流れを維持するためには、交通インフラを管理するための分散型メカニズムが必要です。本稿では、将来の都市道路網を管理するための、市場原理に着想を得た分散型メカニズムを提案します。このメカニズムでは、人間の所有者に代わってソフトウェアエージェントによって操作されるインテリジェントな自律走行車が、インフラと相互作用して、道路網を安全かつ効率的に走行します。ドレスナーとストーンが提案した予約ベースの交差点制御モデルに基づき、単一の交差点と交差点ネットワークの2つの異なるシナリオを検討します。前者では、予約の割り当てに組み合わせオークションに基づく新しいポリシーのパフォーマンスを分析します。後者では、競争市場に着想を得た交通量割り当て戦略がドライバーのルート選択に与える影響を分析します。最後に、オークションベースの交通量制御ポリシーと競争的な交通量割り当て戦略を統合した適応型管理メカニズムを提案します。
Reformulating the Situation Calculus and the Event Calculus in the General Theory of Stable Models and in Answer Set Programming
安定モデルの一般理論と解集合計画法における状況計算と事象計算の再定式化
Circumscription and logic programs under the stable model semantics are two well-known nonmonotonic formalisms. The former has served as a basis of classical logic based action formalisms, such as the situation calculus, the event calculus and temporal action logics; the latter has served as a basis of a family of action languages, such as language A and several of its descendants. Based on the discovery that circumscription and the stable model semantics coincide on a class of canonical formulas, we reformulate the situation calculus and the event calculus in the general theory of stable models. We also present a translation that turns the reformulations further into answer set programs, so that efficient answer set solvers can be applied to compute the situation calculus and the event calculus.
安定モデル意味論に基づくサーカムスクリプションと論理プログラムは、よく知られた非単調な形式主義です。前者は、状況計算、イベント計算、時相アクション論理といった古典論理に基づくアクション形式主義の基礎として機能してきた。後者は、言語Aやその派生言語など、アクション言語ファミリーの基礎として機能してきた。サーカムスクリプションと安定モデル意味論が標準的な論理式のクラスで一致するという発見に基づき、我々は状況計算とイベント計算を安定モデルの一般理論において再定式化します。また、この再定式化をさらに解集合プログラムに変換する翻訳も提示し、効率的な解集合ソルバーを適用して状況計算とイベント計算を計算できるようにします。
Avoiding and Escaping Depressions in Real-Time Heuristic Search
不況の回避と脱出リアルタイムヒューリスティック探索
Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to reach a solution. Early real-time search algorithms, like LRTA*, easily become trapped in those regions since the heuristic values of their states may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms, like LSS-LRTA* or LRTA*(k), improve LRTA*’s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We propose two ways in which depression avoidance can be implemented: mark-and-avoid and move-to-border. We implement these strategies on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is to find a single solution by running the real-time search algorithm once, we show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by one order of magnitude. Of the four new algorithms, daRTAA* produces the best solutions given a fixed deadline on the average time allowed per planning episode. We prove all our algorithms have good theoretical properties: in finite search spaces, they find a solution if one exists, and converge to an optimal after a number of trials.
困難なリアルタイム探索問題を解決するために使用されるヒューリスティックには、窪みのある領域があります。このような領域は、ヒューリスティック関数が解に到達するための実際のコストと比較して不正確である、探索空間の境界付き領域です。LRTA*などの初期のリアルタイム探索アルゴリズムは、状態のヒューリスティック値を複数回更新する必要がある場合があり、コストのかかる解になるため、簡単にこれらの領域に陥ってしまいます。LSS-LRTA*やLRTA*(k)といった最先端のリアルタイム探索アルゴリズムは、LRTA*のヒューリスティック更新メカニズムを改良することで性能向上を実現しています。しかしながら、これらのアルゴリズムは、陥没領域を回避するように探索を誘導するものではありません。本論文では、ヒューリスティックな陥没としてマークされた状態を回避するように探索を誘導する、シンプルなリアルタイム探索原理である陥没回避を提示します。陥没回避の実装方法として、マークアンドアボートと境界移動の2つの方法を提案します。これらの戦略をLSS-LRTA*とRTAA*に実装し、4つの新しいリアルタイムヒューリスティック探索アルゴリズム（aLSS-LRTA*、daLSS-LRTA*、aRTAA*、daRTAA*）を開発しました。リアルタイム探索アルゴリズムを1回実行して単一の解を見つけることを目的とした場合、daLSS-LRTA*とdaRTAA*は、先行アルゴリズムを場合によっては1桁も上回る性能を発揮することを示します。4つの新しいアルゴリズムのうち、daRTAA*は、計画エピソードごとに許容される平均時間という固定された期限が与えられた場合、最良の解を生成します。すべてのアルゴリズムが優れた理論的特性を持つことを証明しました。有限の探索空間において、解が存在する場合はそれを発見し、複数回の試行を経て最適解に収束します。
Proximity-Based Non-uniform Abstractions for Approximate Planning
近似プランニングのための近接性に基づく非一様抽象化
In a deterministic world, a planning agent can be certain of the consequences of its planned sequence of actions. Not so, however, in dynamic, stochastic domains where Markov decision processes are commonly used. Unfortunately these suffer from the `curse of dimensionality’: if the state space is a Cartesian product of many small sets (`dimensions’), planning is exponential in the number of those dimensions.Our new technique exploits the intuitive strategy of selectively ignoring various dimensions in different parts of the state space. The resulting non-uniformity has strong implications, since the approximation is no longer Markovian, requiring the use of a modified planner. We also use a spatial and temporal proximity measure, which responds to continued planning as well as movement of the agent through the state space, to dynamically adapt the abstraction as planning progresses.We present qualitative and quantitative results across a range of experimental domains showing that an agent exploiting this novel approximation method successfully finds solutions to the planning problem using much less than the full state space. We assess and analyse the features of domains which our method can exploit.
決定論的な世界では、計画エージェントは計画された一連の行動の結果を確信できます。しかし、マルコフ決定過程が一般的に使用される動的かつ確率的な領域ではそうではありません。残念ながら、これらは「次元の呪い」に悩まされています。状態空間が多数の小さな集合（「次元」）の直積である場合、計画はそれらの次元の数に対して指数関数的に増加します。私たちの新しい手法は、状態空間のさまざまな部分でさまざまな次元を選択的に無視するという直感的な戦略を活用しています。結果として生じる非均一性は、近似がもはやマルコフ的ではなくなるため、大きな意味を持ち、修正されたプランナーの使用が必要になります。また、計画の継続と状態空間におけるエージェントの移動に応答する空間的および時間的な近接性尺度も使用し、計画の進行に合わせて抽象化を動的に適応させます。この新しい近似法を利用するエージェントは、完全な状態空間よりもはるかに少ない空間を使用して計画問題の解決策をうまく見つけることができることを示す、さまざまな実験領域での定性的および定量的な結果を示します。私たちの方法が活用できる領域の特徴を評価および分析します。
Robust Local Search for Solving RCPSP/max with Durational Uncertainty
持続期間の不確実性を伴うRCPSP/maxを解くためのロバストな局所探索
Scheduling problems in manufacturing, logistics and project management have frequently been modeled using the framework of Resource Constrained Project Scheduling Problems with minimum and maximum time lags (RCPSP/max). Due to the importance of these problems, providing scalable solution schedules for RCPSP/max problems is a topic of extensive research. However, all existing methods for solving RCPSP/max assume that durations of activities are known with certainty, an assumption that does not hold in real world scheduling problems where unexpected external events such as manpower availability, weather changes, etc. lead to delays or advances in completion of activities. Thus, in this paper, our focus is on providing a scalable method for solving RCPSP/max problems with durational uncertainty. To that end, we introduce the robust local search method consisting of three key ideas: (a) Introducing and studying the properties of two decision rule approximations used to compute start times of activities with respect to dynamic realizations of the durational uncertainty; (b) Deriving the expression for robust makespan of an execution strategy based on decision rule approximations; and (c) A robust local search mechanism to efficiently compute activity execution strategies that are robust against durational uncertainty. Furthermore, we also provide enhancements to local search that exploit temporal dependencies between activities. Our experimental results illustrate that robust local search is able to provide robust execution strategies efficiently.
製造、物流、プロジェクト管理におけるスケジューリング問題は、最小および最大のタイムラグを伴うリソース制約付きプロジェクト スケジューリング問題(RCPSP/max)のフレームワークを使用してモデル化されることが多い。これらの問題の重要性から、RCPSP/max問題にスケーラブルなソリューション スケジュールを提供することは、広範な研究のトピックです。しかし、RCPSP/maxを解決するための既存の方法はすべて、アクティビティの期間が確実にわかっていることを前提としているが、この前提は、人材の可用性、天候の変化などの予期しない外部イベントによってアクティビティの完了が遅れたり早まったりする現実世界のスケジューリング問題には当てはまらない。したがって、この論文では、期間の不確実性を伴うRCPSP/max問題をスケーラブルに解決する方法を提供することに焦点を当てる。そのために、次の3つの主要なアイデアで構成されるロバストな局所探索法を導入します。(a)期間の不確実性の動的実現に関するアクティビティの開始時刻を計算するために使用される2つの決定ルール近似を導入し、その特性を調査します。(b)決定ルール近似に基づく実行戦略の堅牢なメイクスパンの式導出、および(c)持続期間の不確実性に対して堅牢なアクティビティ実行戦略を効率的に計算するための堅牢な局所探索メカニズム。さらに、アクティビティ間の時間的依存関係を活用する局所探索の強化も提供します。実験結果は、堅牢な局所探索が堅牢な実行戦略を効率的に提供できることを示しています。
Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice
不完全オントロジー推論システムの完全性保証：理論と実践
To achieve scalability of query answering, the developers of Semantic Web applications are often forced to use incomplete OWL 2 reasoners, which fail to derive all answers for at least one query, ontology, and data set. The lack of completeness guarantees, however, may be unacceptable for applications in areas such as health care and defence, where missing answers can adversely affect the application’s functionality. Furthermore, even if an application can tolerate some level of incompleteness, it is often advantageous to estimate how many and what kind of answers are being lost.In this paper, we present a novel logic-based framework that allows one to check whether a reasoner is complete for a given query Q and ontology T—that is, whether the reasoner is guaranteed to compute all answers to Q w.r.t. T and an arbitrary data set A. Since ontologies and typical queries are often fixed at application design time, our approach allows application developers to check whether a reasoner known to be incomplete in general is actually complete for the kinds of input relevant for the application.We also present a technique that, given a query Q, an ontology T, and reasoners R_1 and R_2 that satisfy certain assumptions, can be used to determine whether, for each data set A, reasoner R_1 computes more answers to Q w.r.t. T and A than reasoner R_2. This allows application developers to select the reasoner that provides the highest degree of completeness for Q and T that is compatible with the application’s scalability requirements.Our results thus provide a theoretical and practical foundation for the design of future ontology-based information systems that maximise scalability while minimising or even eliminating incompleteness of query answers.
クエリ回答のスケーラビリティを実現するために、セマンティックWebアプリケーションの開発者は、少なくとも1つのクエリ、オントロジー、およびデータセットに対するすべての回答を導出できない不完全なOWL 2推論エンジンを使用せざるを得ないことがよくあります。しかし、医療や防衛といった分野では、回答の欠落がアプリケーションの機能に悪影響を及ぼす可能性があるため、完全性の保証がないことは許容できない可能性があります。さらに、アプリケーションがある程度以上の不完全性を許容できる場合でも、失われている回答の数や種類を推定することが有益な場合が多くあります。本稿では、与えられたクエリQとオントロジーTに対して推論エンジンが完全であるかどうか、つまり推論エンジンがQに対するすべての回答を、そのクエリQとオントロジーTに関して計算することが保証されているかどうかを確認できる、新しいロジックベースのフレームワークを提示します。Tと任意のデータセットAから、推論エンジンがQに対して、より詳細な情報を得ることができます。オントロジーと一般的なクエリはアプリケーションの設計時に固定されることが多いため、このアプローチにより、アプリケーション開発者は、一般に不完全だとわかっている推論エンジンが、アプリケーションに関連する種類の入力に対して実際に完全であるかどうかを確認できます。また、クエリQ、オントロジーT、および特定の仮定を満たす推論エンジンR_1とR_2が与えられた場合に、各データセットAについて、推論エンジンR_1が推論エンジンR_2よりも多くの回答をQに対して、TとAに関して計算するかどうかを判定できる手法も紹介します。これにより、アプリケーション開発者は、アプリケーションのスケーラビリティ要件と互換性のある、QとTの完全性が最も高い推論エンジンを選択できます。したがって、私たちの結果は、クエリ回答の不完全さを最小限に抑える、あるいは排除しながらスケーラビリティを最大化する将来のオントロジーベースの情報システムを設計するための理論的かつ実践的な基盤を提供します。
Generalized Biwords for Bitext Compression and Translation Spotting
バイテキスト圧縮と翻訳スポッティングのための一般化バイワード
Large bilingual parallel texts (also known as bitexts) are usually stored in a compressed form, and previous work has shown that they can be more efficiently compressed if the fact that the two texts are mutual translations is exploited. For example, a bitext can be seen as a sequence of biwords —pairs of parallel words with a high probability of co-occurrence— that can be used as an intermediate representation in the compression process. However, the simple biword approach described in the literature can only exploit one-to-one word alignments and cannot tackle the reordering of words. We therefore introduce a generalization of biwords which can describe multi-word expressions and reorderings. We also describe some methods for the binary compression of generalized biword sequences, and compare their performance when different schemes are applied to the extraction of the biword sequence. In addition, we show that this generalization of biwords allows for the implementation of an efficient algorithm to look on the compressed bitext for words or text segments in one of the texts and retrieve their counterpart translations in the other text —an application usually referred to as translation spotting— with only some minor modifications in the compression algorithm.
大規模な二言語対訳テキスト（バイテキストとも呼ばれる）は通常、圧縮形式で保存されますが、これまでの研究で、2つのテキストが相互翻訳であるという事実を利用すれば、より効率的に圧縮できることが示されています。例えば、バイテキストは、圧縮プロセスにおける中間表現として使用できる、共起確率の高い対訳語のペアであるバイワードのシーケンスと見なすことができます。しかし、文献に記載されている単純なバイワードアプローチでは、1対1の単語の対応付けしか利用できず、単語の順序変更には対応できません。そこで、複数単語の表現と順序変更を記述できるバイワードの一般化を導入します。また、一般化されたバイワードシーケンスのバイナリ圧縮手法についても説明し、バイワードシーケンスの抽出に異なる手法を適用した場合のパフォーマンスを比較します。さらに、このバイワードの一般化により、圧縮されたバイテキストから一方のテキストの単語またはテキストセグメントを検索し、もう一方のテキストにある対応する翻訳を取得する効率的なアルゴリズム（通常、翻訳スポッティングと呼ばれるアプリケーション）を、圧縮アルゴリズムにわずかな変更を加えるだけで実装できることを示します。
Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
狭い木幅を活用した全ペア最短経路の計算
We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vertex ordering d. Both algorithms run in O(n^2 w_d) time, where w_d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n^2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In addition, we present a variant that exploits graph separators to arrive at a run time of O(n w_d^2 + n^2 s_d) on general graphs, where s_d <= w_d is the size of the largest minimal separator induced by the vertex ordering d. We show empirically that on both constructed and realistic benchmarks, in many cases the algorithms outperform Floyd-Warshall's as well as Johnson's algorithm, which represent the current state of the art with a run time of O(n^3) and O(nm + n^2 log n), respectively. Our algorithms can be used for spatial and temporal reasoning, such as for the Simple Temporal Problem, which underlines their relevance to the planning and scheduling community.
全ペア最短経路を計算するための、新しく効率的なアルゴリズムを2つ紹介します。これらのアルゴリズムは、実数（負の場合もある）の重みを持つ有向グラフ上で動作します。頂点順序dに沿った有向経路の一貫性を利用します。どちらのアルゴリズムもO(n^2 w_d)時間で実行されます。ここでw_dは、この頂点順序によって生じるグラフ幅です。木幅が一定のグラフでは、これはO(n^2)時間となり、最適です。弦グラフでは、これらのアルゴリズムはO(nm)時間で実行されます。さらに、グラフセパレータを利用することで、一般的なグラフでO(n w_d^2 + n^2 s_d)の実行時間を実現する変種も紹介します。ここでs_d <= w_dは、頂点順序dによって生じる最大最小セパレータのサイズです。我々は、構築されたベンチマークと現実的なベンチマークの両方において、多くの場合、これらのアルゴリズムが、それぞれ実行時間O(n^3)およびO(nm + n^2 log n)で現在の最先端技術であるFloyd-WarshallアルゴリズムおよびJohnsonアルゴリズムよりも優れていることを経験的に示しています。我々のアルゴリズムは、単純な時間問題などの空間推論と時間推論に使用でき、計画とスケジューリングのコミュニティとの関連性を強調しています。
Local Consistency and SAT-Solvers
局所一貫性とSATソルバー
Local consistency techniques such as k-consistency are a key component of specialised solvers for constraint satisfaction problems. In this paper we show that the power of using k-consistency techniques on a constraint satisfaction problem is precisely captured by using a particular inference rule, which we call negative-hyper-resolution, on the standard direct encoding of the problem into Boolean clauses. We also show that current clause-learning SAT-solvers will discover in expected polynomial time any inconsistency that can be deduced from a given set of clauses using negative-hyper-resolvents of a fixed size. We combine these two results to show that, without being explicitly designed to do so, current clause-learning SAT-solvers efficiently simulate k-consistency techniques, for all fixed values of k. We then give some experimental results to show that this feature allows clause-learning SAT-solvers to efficiently solve certain families of constraint problems which are challenging for conventional constraint-programming solvers.
k-一貫性などの局所一貫性手法は、制約充足問題に特化したソルバーの重要な構成要素です。本論文では、制約充足問題におけるk-一貫性手法の有効性が、問題をブール節に直接符号化する標準的な手法に対して、負の超解像度と呼ぶ特定の推論規則を適用することで正確に表現されることを示します。また、現在の節学習型SATソルバーは、固定サイズの負の超解像度を用いて、与えられた節集合から推論できる矛盾を、期待される多項式時間で発見できることを示します。これら2つの結果を組み合わせることで、既存の節学習型SATソルバーは、明示的に設計されているわけではないものの、kのあらゆる固定値に対してk-一貫性技法を効率的にシミュレートできることを示します。さらに、この機能により、節学習型SATソルバーは、従来の制約プログラミングソルバーでは困難であった特定の制約問題を効率的に解くことができることを示す実験結果を示します。
SAS+ Planning as Satisfiability
充足可能性としてのSAS+プランニング
Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme (SASE) based on the SAS+ formalism. The new scheme exploits the structural information in SAS+, resulting in an encoding that is both more compact and efficient for planning. We prove the correctness of the new encoding by establishing an isomorphism between the solution plans of SASE and that of STRIPS based encodings. We further analyze the transition variables newly introduced in SASE to explain why it accommodates modern SAT solving algorithms and improves performance. We give empirical statistical results to support our analysis. We also develop a number of techniques to further reduce the encoding size of SASE, and conduct experimental studies to show the strength of each individual technique. Finally, we report extensive experimental results to demonstrate significant improvements of SASE over the state-of-the-art STRIPS based encoding schemes in terms of both time and memory efficiency.
プランニングを充足可能性として捉えることは、多くの顕著な利点を持つプランニングへの主要なアプローチです。既存のプランニングを充足可能性として捉える手法では、通常、STRIPSからコンパイルされたエンコーディングが用いられます。本研究では、SAS+形式に基づく新たなSATエンコーディングスキーム（SASE）を導入します。この新スキームはSAS+の構造情報を活用し、よりコンパクトかつ効率的なプランニングを実現するエンコーディングを実現します。SASEの解プランとSTRIPSベースのエンコーディングの解プランの間に同型性を確立することで、この新エンコーディングの正しさを証明します。さらに、SASEで新たに導入された遷移変数を分析し、SASEが最新のSAT解法アルゴリズムに対応し、パフォーマンスを向上させる理由を説明します。また、本分析を裏付ける実証的な統計結果も示します。SASEの符号化サイズをさらに削減するための複数の手法を開発し、各手法の有効性を示す実験的研究を実施しました。最後に、SASEが最先端のSTRIPSベースの符号化方式と比較して、時間とメモリ効率の両面で大幅に改善されていることを示す広範な実験結果を報告します。
Consistency Techniques for Flow-Based Projection-Safe Global Cost Functions in Weighted Constraint Satisfaction
重み付き制約充足におけるフローベースの射影安全グローバルコスト関数のための一貫性手法
Many combinatorial problems deal with preferences and violations, the goal of which is to find solutions with the minimum cost. Weighted constraint satisfaction is a framework for modeling such problems, which consists of a set of cost functions to measure the degree of violation or preferences of different combinations of variable assignments. Typical solution methods for weighted constraint satisfaction problems (WCSPs) are based on branch-and-bound search, which are made practical through the use of powerful consistency techniques such as AC*, FDAC*, EDAC* to deduce hidden cost information and value pruning during search. These techniques, however, are designed to be efficient only on binary and ternary cost functions which are represented in table form. In tackling many real-life problems, high arity (or global) cost functions are required. We investigate efficient representation scheme and algorithms to bring the benefits of the consistency techniques to also high arity cost functions, which are often derived from hard global constraints from classical constraint satisfaction.The literature suggests some global cost functions can be represented as flow networks, and the minimum cost flow algorithm can be used to compute the minimum costs of such networks in polynomial time. We show that naive adoption of this flow-based algorithmic method for global cost functions can result in a stronger form of null-inverse consistency. We further show how the method can be modified to handle cost projections and extensions to maintain generalized versions of AC* and FDAC* for cost functions with more than two variables. Similar generalization for the stronger EDAC* is less straightforward. We reveal the oscillation problem when enforcing EDAC* on cost functions sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC* and generalize it to weak EDGAC* for non-binary cost functions. Using various benchmarks involving the soft variants of hard global constraints ALLDIFFERENT, GCC, SAME, and REGULAR, empirical results demonstrate that our proposal gives improvements of up to an order of magnitude when compared with the traditional constraint optimization approach, both in terms of time and pruning.
多くの組み合わせ問題は、優先順位と違反を扱い、その目標は最小コストの解を見つけることです。重み付き制約満足度は、このような問題をモデル化するフレームワークで、違反の度合いや変数割り当てのさまざまな組み合わせの優先順位を測定するための一連のコスト関数で構成されます。重み付き制約満足度問題(WCSP)の一般的な解決法は分岐限定探索に基づいています。分岐限定探索は、AC*、FDAC*、EDAC*などの強力な一貫性手法を使用して隠れたコスト情報を推測し、探索中に値を刈り込むことで実用化されます。ただし、これらの手法は、表形式で表される2値および3値のコスト関数に対してのみ効率的になるように設計されています。多くの実際の問題に対処するには、高アリティ(またはグローバル)のコスト関数が必要です。我々は、一貫性手法の利点を、古典的な制約充足からのハードグローバル制約から導出されることが多い高アリティコスト関数にももたらすための効率的な表現スキームとアルゴリズムを調査します。文献では、一部のグローバルコスト関数はフローネットワークとして表現でき、最小コストフローアルゴリズムを使用してそのようなネットワークの最小コストを多項式時間で計算できることが示唆されています。このフローベースのアルゴリズム手法をグローバルコスト関数に単純に採用することで、より強力なヌル逆一貫性が得られることを示します。さらに、コスト射影と拡張を処理して、2つ以上の変数を持つコスト関数に対してAC*とFDAC*の一般化バージョンを維持するようにこの手法を変更する方法を示します。より強力なEDAC*に対する同様の一般化はそれほど簡単ではありません。複数の変数を共有するコスト関数にEDAC*を適用すると振動問題が発生することを明らかにし、振動を回避するために、EDAC*の弱いバージョンを提案し、それを非バイナリコスト関数の弱いEDGAC*に一般化します。ハードグローバル制約のソフトバリアントであるALLDIFFERENT、GCC、SAME、およびREGULARを含む様々なベンチマークを用いた実験結果により、本提案は従来の制約最適化アプローチと比較して、時間と枝刈りの両面で最大1桁の改善をもたらすことが実証されました。
Exploiting Model Equivalences for Solving Interactive Dynamic Influence Diagrams
インタラクティブな動的影響図を解くためのモデル同値性の活用
We focus on the problem of sequential decision making in partially observable environments shared with other agents of uncertain types having similar or conflicting objectives. This problem has been previously formalized by multiple frameworks one of which is the interactive dynamic influence diagram (I-DID), which generalizes the well-known influence diagram to the multiagent setting. I-DIDs are graphical models and may be used to compute the policy of an agent given its belief over the physical state and others’ models, which changes as the agent acts and observes in the multiagent setting. As we may expect, solving I-DIDs is computationally hard. This is predominantly due to the large space of candidate models ascribed to the other agents and its exponential growth over time. We present two methods for reducing the size of the model space and stemming its exponential growth. Both these methods involve aggregating individual models into equivalence classes. Our first method groups together behaviorally equivalent models and selects only those models for updating which will result in predictive behaviors that are distinct from others in the updated model space. The second method further compacts the model space by focusing on portions of the behavioral predictions. Specifically, we cluster actionally equivalent models that prescribe identical actions at a single time step. Exactly identifying the equivalences would require us to solve all models in the initial set. We avoid this by selectively solving some of the models, thereby introducing an approximation. We discuss the error introduced by the approximation, and empirically demonstrate the improved efficiency in solving I-DIDs due to the equivalences.
我々は、類似または相反する目的を持つ不確実なタイプの他のエージェントと共有される、部分的に観測可能な環境における逐次的な意思決定の問題に焦点を当てます。この問題はこれまで複数のフレームワークによって形式化されており、その1つがインタラクティブ・ダイナミック・インフルエンス・ダイアグラム（I-DID）です。これは、よく知られているインフルエンス・ダイアグラムをマルチエージェント環境に一般化したものです。I-DIDはグラフィカルモデルであり、エージェントがマルチエージェント環境において行動し観察するにつれて変化する、物理状態と他のエージェントのモデルに関する信念に基づいて、エージェントのポリシーを計算するために使用できます。予想どおり、I-DIDの解決は計算的に困難です。これは主に、他のエージェントに帰属する候補モデルの空間が広大であり、それが時間の経過とともに指数関数的に増加することが原因です。我々は、モデル空間のサイズを縮小し、その指数関数的な増加を食い止める2つの手法を提示します。どちらの手法も、個々のモデルを同値クラスに集約することを伴います。最初の手法では、行動的に等価なモデルをグループ化し、更新後のモデル空間において他のモデルとは異なる予測行動をもたらすモデルのみを更新対象として選択します。2つ目の手法では、行動予測の一部に焦点を当てることで、モデル空間をさらにコンパクト化します。具体的には、単一のタイムステップで同一の行動を規定する、行動的に等価なモデルをクラスタリングします。等価性を正確に特定するには、初期セット内のすべてのモデルを解く必要があります。本手法では、一部のモデルを選択的に解くことで近似値を導入し、この近似値によって生じる誤差について考察し、等価性によってI-DIDの解法効率が向上することを実証的に示します。
Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems
計数ベースの探索：制約充足問題のための分岐ヒューリスティック
Designing a search heuristic for constraint programming that is reliable across problem domains has been an important research topic in recent years. This paper concentrates on one family of candidates: counting-based search. Such heuristics seek to make branching decisions that preserve most of the solutions by determining what proportion of solutions to each individual constraint agree with that decision. Whereas most generic search heuristics in constraint programming rely on local information at the level of the individual variable, our search heuristics are based on more global information at the constraint level. We design several algorithms that are used to count the number of solutions to specific families of constraints and propose some search heuristics exploiting such information. The experimental part of the paper considers eight problem domains ranging from well-established benchmark puzzles to rostering and sport scheduling. An initial empirical analysis identifies heuristic maxSD as a robust candidate among our proposals.eWe then evaluate the latter against the state of the art, including the latest generic search heuristics, restarts, and discrepancy-based tree traversals. Experimental results show that counting-based search generally outperforms other generic heuristics.
制約プログラミングにおいて、問題領域を横断して信頼性の高い探索ヒューリスティックの設計は、近年重要な研究課題となっています。本論文では、候補の一つである計数ベース探索に焦点を当てます。このようなヒューリスティックは、個々の制約に対する解のうち、どの程度の割合がその決定に合致するかを判断することで、解の大部分を保持する分岐決定を行おうとします。制約プログラミングにおける一般的な探索ヒューリスティックの多くは、個々の変数レベルの局所的な情報に依存していますが、本論文の探索ヒューリスティックは、制約レベルのよりグローバルな情報に基づいています。特定の制約群に対する解の数を計数するアルゴリズムをいくつか設計し、そのような情報を活用する探索ヒューリスティックをいくつか提案します。本論文の実験部分では、定評のあるベンチマークパズルから選手編成やスポーツのスケジューリングに至るまで、8つの問題領域を取り上げます。最初の実証分析では、提案されたヒューリスティックの中で、maxSDヒューリスティックが堅牢な候補であることが示されました。次に、maxSDヒューリスティックを、最新の一般的な探索ヒューリスティック、リスタート、不一致に基づくツリー探索などの最先端技術と比較して評価します。実験結果は、計数に基づく探索が一般的に他の一般的なヒューリスティックよりも優れていることを示しています。
The CQC Algorithm: Cycling in Graphs to Semantically Enrich and Enhance a Bilingual Dictionary
CQCアルゴリズム：グラフのサイクリングによるバイリンガル辞書の意味的拡充と拡張
Bilingual machine-readable dictionaries are knowledge resources useful in many automatic tasks. However, compared to monolingual computational lexicons like WordNet, bilingual dictionaries typically provide a lower amount of structured information, such as lexical and semantic relations, and often do not cover the entire range of possible translations for a word of interest. In this paper we present Cycles and Quasi-Cycles (CQC), a novel algorithm for the automated disambiguation of ambiguous translations in the lexical entries of a bilingual machine-readable dictionary. The dictionary is represented as a graph, and cyclic patterns are sought in the graph to assign an appropriate sense tag to each translation in a lexical entry. Further, we use the algorithm’s output to improve the quality of the dictionary itself, by suggesting accurate solutions to structural problems such as misalignments, partial alignments and missing entries. Finally, we successfully apply CQC to the task of synonym extraction.
機械可読な二言語辞書は、多くの自動タスクにおいて有用な知識リソースです。しかし、WordNetのような単一言語の計算辞書と比較すると、二言語辞書は一般的に、語彙関係や意味関係といった構造化情報の量が少なく、対象単語の翻訳可能な範囲全体を網羅していないことがよくあります。本稿では、機械可読な二言語辞書の語彙項目における曖昧な翻訳を自動的に解消する新しいアルゴリズム、Cycles and Quasi-Cycles (CQC)を紹介します。辞書はグラフとして表現され、グラフ内の循環パターンを探すことで、語彙項目内の各翻訳に適切な意味タグを割り当てます。さらに、このアルゴリズムの出力を用いて、不整合、部分的な整合、項目の欠落といった構造上の問題に対する正確な解決策を提案することで、辞書自体の品質を向上させます。最後に、CQCを同義語抽出タスクに適用することに成功しました。
Learning and Reasoning with Action-Related Places for Robust Mobile Manipulation
ロバストなモバイル操作のための行動関連場所を用いた学習と推論
We propose the concept of Action-Related Place (ARPlace) as a powerful and flexible representation of task-related place in the context of mobile manipulation. ARPlace represents robot base locations not as a single position, but rather as a collection of positions, each with an associated probability that the manipulation action will succeed when located there. ARPlaces are generated using a predictive model that is acquired through experience-based learning, and take into account the uncertainty the robot has about its own location and the location of the object to be manipulated.When executing the task, rather than choosing one specific goal position based only on the initial knowledge about the task context, the robot instantiates an ARPlace, and bases its decisions on this ARPlace, which is updated as new information about the task becomes available. To show the advantages of this least-commitment approach, we present a transformational planner that reasons about ARPlaces in order to optimize symbolic plans. Our empirical evaluation demonstrates that using ARPlaces leads to more robust and efficient mobile manipulation in the face of state estimation uncertainty on our simulated robot.
我々は、モバイルマニピュレーションのコンテキストにおけるタスク関連場所の強力かつ柔軟な表現として、アクション関連場所（ARPlace）の概念を提案します。ARPlaceは、ロボットの拠点位置を単一の位置としてではなく、位置の集合として表し、各位置は、そこに配置した場合にマニピュレーションアクションが成功する確率に関連付けられています。ARPlaceは、経験に基づく学習によって獲得された予測モデルを使用して生成され、ロボット自身の位置と操作対象の位置に関する不確実性を考慮に入れます。タスクを実行する際、ロボットはタスクコンテキストに関する初期知識のみに基づいて特定の目標位置を選択するのではなく、ARPlaceをインスタンス化し、このARPlaceに基づいて決定を下します。ARPlaceは、タスクに関する新しい情報が利用可能になると更新されます。この最小コミットメントアプローチの利点を示すため、記号計画を最適化するためにARPlaceを推論する変換型プランナーを提示します。実証的評価により、シミュレーションロボットにおいて状態推定の不確実性を考慮した上で、ARPlaceの使用により、より堅牢で効率的な移動操作が実現できることが示されました。