Towards Flexible Teamwork
柔軟なチームワークに向けて
Many AI researchers are today striving to build agent teams for complex, dynamic multi-agent domains, with intended applications in arenas such as education, training, entertainment, information integration, and collective robotics. Unfortunately, uncertainties in these complex, dynamic domains obstruct coherent teamwork. In particular, team members often encounter differing, incomplete, and possibly inconsistent views of their environment. Furthermore, team members can unexpectedly fail in fulfilling responsibilities or discover unexpected opportunities. Highly flexible coordination and communication is key in addressing such uncertainties. Simply fitting individual agents with precomputed coordination plans will not do, for their inflexibility can cause severe failures in teamwork, and their domain-specificity hinders reusability. Our central hypothesis is that the key to such flexibility and reusability is providing agents with general models of teamwork. Agents exploit such models to autonomously reason about coordination and communication, providing requisite flexibility. Furthermore, the models enable reuse across domains, both saving implementation effort and enforcing consistency. This article presents one general, implemented model of teamwork, called STEAM. The basic building block of teamwork in STEAM is joint intentions (Cohen & Levesque, 1991b); teamwork in STEAM is based on agents’ building up a (partial) hierarchy of joint intentions (this hierarchy is seen to parallel Grosz & Kraus’s partial SharedPlans, 1996). Furthermore, in STEAM, team members monitor the team’s and individual members’ performance, reorganizing the team as necessary. Finally, decision-theoretic communication selectivity in STEAM ensures reduction in communication overheads of teamwork, with appropriate sensitivity to the environmental conditions. This article describes STEAM’s application in three different complex domains, and presents detailed empirical results.
多くのAI研究者は、今日、教育、トレーニング、エンターテイメント、情報統合、集団ロボティクスなどの分野への応用を目的とした、複雑で動的なマルチエージェント領域向けのエージェントチームの構築に取り組んでいます。残念ながら、これらの複雑で動的な領域における不確実性は、首尾一貫したチームワークを妨げます。特に、チームメンバーは、環境に対する異なる、不完全な、そしておそらくは矛盾した認識に遭遇することがよくあります。さらに、チームメンバーは予期せず責任を果たせなかったり、予期せぬ機会を発見したりすることもあります。このような不確実性に対処するには、非常に柔軟な調整とコミュニケーションが鍵となります。個々のエージェントに事前計算された調整計画を単純に当てはめるだけでは不十分です。柔軟性に欠けるため、チームワークに重大な欠陥が生じる可能性があり、また、ドメイン特異性により再利用性が阻害されるからです。私たちの中心的な仮説は、このような柔軟性と再利用性の鍵は、エージェントにチームワークの汎用モデルを提供することである、というものです。エージェントはこのようなモデルを活用して、調整とコミュニケーションについて自律的に推論し、必要な柔軟性を提供します。さらに、これらのモデルはドメイン間の再利用を可能にし、実装の労力を削減するとともに、一貫性を強化します。本稿では、STEAMと呼ばれる、実装済みの汎用チームワークモデルを紹介します。STEAMにおけるチームワークの基本的な構成要素は共同意図です（Cohen & Levesque, 1991b）。STEAMにおけるチームワークは、エージェントが共同意図の（部分的な）階層を構築することに基づいています（この階層は、Grosz & Krausの部分的なSharedPlans, 1996に類似していると考えられています）。さらに、STEAMでは、チームメンバーはチーム全体および個々のメンバーのパフォーマンスを監視し、必要に応じてチームを再編成します。最後に、STEAMにおける意思決定理論に基づくコミュニケーション選択性は、環境条件への適切な感度を保ちながら、チームワークにおけるコミュニケーションオーバーヘッドの削減を保証します。本稿では、3つの異なる複雑な領域におけるSTEAMの適用例を説明し、詳細な実証結果を提示します。
Identifying Hierarchical Structure in Sequences: A linear-time algorithm
シーケンスにおける階層構造の識別：線形時間アルゴリズム
SEQUITUR is an algorithm that infers a hierarchical structure from a sequence of discrete symbols by replacing repeated phrases with a grammatical rule that generates the phrase, and continuing this process recursively. The result is a hierarchical representation of the original sequence, which offers insights into its lexical structure. The algorithm is driven by two constraints that reduce the size of the grammar, and produce structure as a by-product. SEQUITUR breaks new ground by operating incrementally. Moreover, the method’s simple structure permits a proof that it operates in space and time that is linear in the size of the input. Our implementation can process 50,000 symbols per second and has been applied to an extensive range of real world sequences.
SEQUITURは、繰り返されるフレーズをそのフレーズを生成する文法規則に置き換え、このプロセスを再帰的に続けることで、離散記号のシーケンスから階層構造を推論するアルゴリズムです。その結果、元のシーケンスの階層的表現が得られ、その語彙構造に関する洞察が得られます。このアルゴリズムは、文法のサイズを縮小し、副産物として構造を生成するという2つの制約によって駆動されます。SEQUITURは、段階的に動作することで新たな境地を切り開きます。さらに、この手法のシンプルな構造により、入力のサイズに線形な空間と時間で動作することが証明されます。私たちの実装は毎秒50,000シンボルを処理でき、実世界の幅広いシーケンスに適用されています。
A New Look at the Easy-Hard-Easy Pattern of Combinatorial Search Difficulty
組み合わせ探索の難しさにおける容易-困難-容易パターンの新たな考察
The easy-hard-easy pattern in the difficulty of combinatorial search problems as constraints are added has been explained as due to a competition between the decrease in number of solutions and increased pruning. We test the generality of this explanation by examining one of its predictions: if the number of solutions is held fixed by the choice of problems, then increased pruning should lead to a monotonic decrease in search cost. Instead, we find the easy-hard-easy pattern in median search cost even when the number of solutions is held constant, for some search methods. This generalizes previous observations of this pattern and shows that the existing theory does not explain the full range of the peak in search cost. In these cases the pattern appears to be due to changes in the size of the minimal unsolvable subproblems, rather than changing numbers of solutions.
制約条件が追加されるにつれて、組み合わせ探索問題の難易度が「簡単-難しい-簡単」というパターンに変化する理由は、解の数の減少と枝刈りの増加との競合によるものと説明されてきた。我々は、この説明の予測の一つを検証することで、この説明の一般性を検証します。すなわち、問題の選択によって解の数が一定に保たれる場合、枝刈りの増加は探索コストの単調減少につながるはずです。ところが、実際には、いくつかの探索手法において、解の数が一定に保たれている場合でも、平均探索コストが「簡単-難しい-簡単」というパターンを示すことがわかった。これは、このパターンに関するこれまでの観察結果を一般化するものであり、既存の理論では探索コストのピークの全範囲を説明できないことを示しています。これらの場合、このパターンは解の数の変化ではなく、最小の解決不可能な部分問題のサイズの変化によるものと思われます。
Bidirectional Heuristic Search Reconsidered
双方向ヒューリスティック探索の再考
The assessment of bidirectional heuristic search has been incorrect since it was first published more than a quarter of a century ago. For quite a long time, this search strategy did not achieve the expected results, and there was a major misunderstanding about the reasons behind it. Although there is still wide-spread belief that bidirectional heuristic search is afflicted by the problem of search frontiers passing each other, we demonstrate that this conjecture is wrong. Based on this finding, we present both a new generic approach to bidirectional heuristic search and a new approach to dynamically improving heuristic values that is feasible in bidirectional search only. These approaches are put into perspective with both the traditional and more recently proposed approaches in order to facilitate a better overall understanding. Empirical results of experiments with our new approaches show that bidirectional heuristic search can be performed very efficiently and also with limited memory. These results suggest that bidirectional heuristic search appears to be better for solving certain difficult problems than corresponding unidirectional search. This provides some evidence for the usefulness of a search strategy that was long neglected. In summary, we show that bidirectional heuristic search is viable and consequently propose that it be reconsidered.
双方向ヒューリスティック探索の評価は、25年以上前に初めて発表されて以来、誤ったものであった。この探索戦略は長らく期待通りの結果を達成できず、その理由について大きな誤解がありました。双方向ヒューリスティック探索は探索フロンティアが互いにすれ違うという問題に悩まされるという通説が依然として広く信じられていますが、我々はこの推測が誤りであることを証明します。この発見に基づき、双方向ヒューリスティック探索に対する新しい汎用的なアプローチと、双方向探索でのみ実行可能なヒューリスティック値を動的に改善する新しいアプローチを提示します。これらのアプローチは、より包括的な理解を深めるために、従来のアプローチと最近提案されたアプローチの両方と比較検討されます。我々の新しいアプローチを用いた実験の結果は、双方向ヒューリスティック探索が非常に効率的に、かつ限られたメモリでも実行可能であることを示しています。これらの結果は、特定の困難な問題を解決するには、対応する単方向探索よりも双方向ヒューリスティック探索の方が優れていることを示唆しています。これは、長らく無視されてきた探索戦略の有用性を示す証拠となります。要約すると、双方向ヒューリスティック探索は実行可能であることを示し、再検討を提案します。
Eight Maximal Tractable Subclasses of Allen’s Algebra with Metric Time
計量時間を伴うアレン代数の8つの最大扱いやすいサブクラス
This paper combines two important directions of research in temporal resoning: that of finding maximal tractable subclasses of Allen’s interval algebra, and that of reasoning with metric temporal information. Eight new maximal tractable subclasses of Allen’s interval algebra are presented, some of them subsuming previously reported tractable algebras. The algebras allow for metric temporal constraints on interval starting or ending points, using the recent framework of Horn DLRs. Two of the algebras can express the notion of sequentiality between intervals, being the first such algebras admitting both qualitative and metric time.
本論文は、時間推論における2つの重要な研究方向、すなわちアレンの区間代数の最大扱いやすいサブクラスを見つける研究と、計量時間情報を用いた推論という方向性を統合します。アレンの区間代数の8つの新しい最大扱いやすいサブクラスが提示され、そのいくつかは以前に報告された扱いやすい代数を包含します。これらの代数は、最近のホーンDLRの枠組みを用いて、区間の開始点または終了点に計量時間制約を課すことができます。2つの代数は区間間の連続性の概念を表現でき、質的時間と計量時間の両方を許容する最初の代数です。
When Gravity Fails: Local Search Topology
重力が崩壊するとき：局所探索トポロジー
Local search algorithms for combinatorial search problems frequently encounter a sequence of states in which it is impossible to improve the value of the objective function; moves through these regions, called plateau moves, dominate the time spent in local search. We analyze and characterize plateaus for three different classes of randomly generated Boolean Satisfiability problems. We identify several interesting features of plateaus that impact the performance of local search algorithms. We show that local minima tend to be small but occasionally may be very large. We also show that local minima can be escaped without unsatisfying a large number of clauses, but that systematically searching for an escape route may be computationally expensive if the local minimum is large. We show that plateaus with exits, called benches, tend to be much larger than minima, and that some benches have very few exit states which local search can use to escape. We show that the solutions (i.e., global minima) of randomly generated problem instances form clusters, which behave similarly to local minima. We revisit several enhancements of local search algorithms and explain their performance in light of our results. Finally we discuss strategies for creating the next generation of local search algorithms.
組合せ探索問題に対する局所探索アルゴリズムは、目的関数の値を改善できない状態のシーケンスに頻繁に遭遇します。これらの領域を通過する動き（プラトー移動）は、局所探索に費やされる時間の大部分を占めます。ランダムに生成されたブール充足可能性問題の3つの異なるクラスについて、プラトーを解析し、その特徴を明らかにします。局所探索アルゴリズムの性能に影響を与えるプラトーの興味深い特徴をいくつか特定します。局所最小値は小さい傾向にありますが、時には非常に大きくなる可能性があることを示します。また、局所最小値は多数の節を不満足にすることなく脱出できますが、局所最小値が大きい場合、脱出経路を系統的に探索することは計算コストが高くなる可能性があることも示します。出口を持つプラトー（ベンチ）は、最小値よりもはるかに大きくなる傾向があり、一部のベンチでは、局所探索が脱出に使用できる出口状態が非常に少ないことを示します。ランダムに生成された問題インスタンスの解（すなわち、大域的最小値）はクラスターを形成し、それが局所最小値と同様に振る舞うことを示します。我々は局所探索アルゴリズムのいくつかの改良点を再検討し、我々の研究結果を踏まえてそれらの性能を説明します。最後に、次世代の局所探索アルゴリズムを作成するための戦略について議論します。
Dynamic Non-Bayesian Decision Making
動的非ベイズ的意思決定
The model of a non-Bayesian agent who faces a repeated game with incomplete information against Nature is an appropriate tool for modeling general agent-environment interactions. In such a model the environment state (controlled by Nature) may change arbitrarily, and the feedback/reward function is initially unknown. The agent is not Bayesian, that is he does not form a prior probability neither on the state selection strategy of Nature, nor on his reward function. A policy for the agent is a function which assigns an action to every history of observations and actions. Two basic feedback structures are considered. In one of them — the perfect monitoring case — the agent is able to observe the previous environment state as part of his feedback, while in the other — the imperfect monitoring case — all that is available to the agent is the reward obtained. Both of these settings refer to partially observable processes, where the current environment state is unknown. Our main result refers to the competitive ratio criterion in the perfect monitoring case. We prove the existence of an efficient stochastic policy that ensures that the competitive ratio is obtained at almost all stages with an arbitrarily high probability, where efficiency is measured in terms of rate of convergence. It is further shown that such an optimal policy does not exist in the imperfect monitoring case. Moreover, it is proved that in the perfect monitoring case there does not exist a deterministic policy that satisfies our long run optimality criterion. In addition, we discuss the maxmin criterion and prove that a deterministic efficient optimal strategy does exist in the imperfect monitoring case under this criterion. Finally we show that our approach to long-run optimality can be viewed as qualitative, which distinguishes it from previous work in this area.
不完全情報を用いて自然を相手に繰り返しゲームに臨む非ベイズエージェントのモデルは、一般的なエージェントと環境の相互作用をモデル化するための適切なツールです。このようなモデルでは、環境状態（自然によって制御される）は任意に変化する可能性があり、フィードバック/報酬関数は最初は未知です。エージェントはベイズ的ではない。つまり、自然の状態選択戦略にも報酬関数にも事前確率を形成しない。エージェントのポリシーとは、観測と行動の履歴すべてにアクションを割り当てる関数です。2つの基本的なフィードバック構造が検討されています。1つは完全な監視の場合で、エージェントはフィードバックの一部として以前の環境状態を観測できます。もう1つは不完全な監視の場合で、エージェントが利用できるのは獲得した報酬だけです。これらの設定は両方とも、現在の環境状態が不明な、部分的に観測可能なプロセスを指します。私たちの主な結果は、完全な監視の場合の競争比率基準に関するものです。ほぼすべての段階で任意の高い確率で競争比率が得られることを保証する効率的な確率的ポリシーの存在を証明します。ここで、効率は収束速度で測定されます。さらに、そのような最適なポリシーは不完全な監視の場合には存在しないことが示されます。さらに、完全な監視の場合には、私たちの長期最適性基準を満たす決定論的ポリシーは存在しないことが証明されています。さらに、マックスミニ基準について議論し、この基準の下では不完全監視の場合に決定論的に効率的な最適戦略が存在することを証明します。最後に、長期最適性に対する我々のアプローチは定性的なものと見なすことができ、この点でこの分野における先行研究とは異なることを示す。
A Model Approximation Scheme for Planning in Partially Observable Stochastic Domains
部分観測確率領域におけるプランニングのためのモデル近似スキーム
Partially observable Markov decision processes (POMDPs) are a natural model for planning problems where effects of actions are nondeterministic and the state of the world is not completely observable. It is difficult to solve POMDPs exactly. This paper proposes a new approximation scheme. The basic idea is to transform a POMDP into another one where additional information is provided by an oracle. The oracle informs the planning agent that the current state of the world is in a certain region. The transformed POMDP is consequently said to be region observable. It is easier to solve than the original POMDP. We propose to solve the transformed POMDP and use its optimal policy to construct an approximate policy for the original POMDP. By controlling the amount of additional information that the oracle provides, it is possible to find a proper tradeoff between computational time and approximation quality. In terms of algorithmic contributions, we study in details how to exploit region observability in solving the transformed POMDP. To facilitate the study, we also propose a new exact algorithm for general POMDPs. The algorithm is conceptually simple and yet is significantly more efficient than all previous exact algorithms.
部分観測マルコフ決定過程（POMDP）は、アクションの効果が非決定論的で、世界の状態が完全に観測可能ではない計画問題のための自然なモデルです。POMDPを正確に解くことは困難です。本論文では、新しい近似スキームを提案します。基本的な考え方は、POMDPを、オラクルによって追加情報が提供される別のPOMDPに変換することです。オラクルは、計画エージェントに、世界の現在の状態が特定の領域にあることを通知します。変換されたPOMDPは、領域観測可能と呼ばれます。元のPOMDPよりも簡単に解くことができます。我々は、変換されたPOMDPを解き、その最適ポリシーを用いて元のPOMDPの近似ポリシーを構築することを提案します。オラクルが提供する追加情報の量を制御することで、計算時間と近似品質の適切なトレードオフを見つけることが可能です。アルゴリズムの貢献という点では、変換されたPOMDPを解く際に領域観測性をどのように活用するかを詳細に検討します。また、研究を容易にするために、一般的なPOMDPのための新しい厳密アルゴリズムも提案します。このアルゴリズムは概念的には単純であるが、これまでのすべての厳密アルゴリズムよりもはるかに効率的です。
Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures
検索失敗の説明に基づく解析によるプラン導出の保存とインデックス作成
Case-Based Planning (CBP) provides a way of scaling up domain-independent planning to solve large problems in complex domains. It replaces the detailed and lengthy search for a solution with the retrieval and adaptation of previous planning experiences. In general, CBP has been demonstrated to improve performance over generative (from-scratch) planning. However, the performance improvements it provides are dependent on adequate judgements as to problem similarity. In particular, although CBP may substantially reduce planning effort overall, it is subject to a mis-retrieval problem. The success of CBP depends on these retrieval errors being relatively rare. This paper describes the design and implementation of a replay framework for the case-based planner DERSNLP+EBL. DERSNLP+EBL extends current CBP methodology by incorporating explanation-based learning techniques that allow it to explain and learn from the retrieval failures it encounters. These techniques are used to refine judgements about case similarity in response to feedback when a wrong decision has been made. The same failure analysis is used in building the case library, through the addition of repairing cases. Large problems are split and stored as single goal subproblems. Multi-goal problems are stored only when these smaller cases fail to be merged into a full solution. An empirical evaluation of this approach demonstrates the advantage of learning from experienced retrieval failure.
事例ベースプランニング（CBP）は、複雑な領域における大規模問題を解決するために、領域に依存しないプランニングをスケールアップする方法を提供します。CBPは、詳細かつ長時間を要する解決策の探索を、過去のプランニング経験の検索と適応に置き換えます。一般的に、CBPは生成型（ゼロからの）プランニングよりも性能向上が実証されています。しかし、CBPが提供する性能向上は、問題の類似性に関する適切な判断に依存します。特に、CBPは全体的なプランニング労力を大幅に削減できるものの、誤検索の問題に悩まされます。CBPの成功は、これらの検索エラーが比較的まれであることにかかっています。本稿では、事例ベースプランナーDERSNLP+EBLのリプレイフレームワークの設計と実装について説明します。DERSNLP+EBLは、説明に基づく学習手法を組み込むことで、現在のCBP手法を拡張します。この手法は、遭遇する検索の失敗を説明し、そこから学習することを可能にします。これらの手法は、誤った決定が行われた際のフィードバックに応じて、事例の類似性に関する判断を改善するために使用されます。同じ障害分析は、修復ケースを追加することで、ケースライブラリの構築にも使用されます。大きな問題は分割され、単一目標のサブ問題として保存されます。複数目標の問題は、これらの小さなケースが完全なソリューションに統合されなかった場合にのみ保存されます。このアプローチの実証的評価は、経験豊富な検索失敗から学習することの利点を示しています。
Analysis of Three-Dimensional Protein Images
3次元タンパク質画像の解析
A fundamental goal of research in molecular biology is to understand protein structure. Protein crystallography is currently the most successful method for determining the three-dimensional (3D) conformation of a protein, yet it remains labor intensive and relies on an expert’s ability to derive and evaluate a protein scene model. In this paper, the problem of protein structure determination is formulated as an exercise in scene analysis. A computational methodology is presented in which a 3D image of a protein is segmented into a graph of critical points. Bayesian and certainty factor approaches are described and used to analyze critical point graphs and identify meaningful substructures, such as alpha-helices and beta-sheets. Results of applying the methodologies to protein images at low and medium resolution are reported. The research is related to approaches to representation, segmentation and classification in vision, as well as to top-down approaches to protein structure prediction.
分子生物学研究の基本的な目標は、タンパク質構造を理解することです。タンパク質結晶構造解析は現在、タンパク質の3次元（3D）構造を決定する最も成功した方法ですが、依然として労働集約的であり、タンパク質シーンモデルの導出と評価には専門家の能力に依存しています。本論文では、タンパク質構造決定の問題をシーン分析の演習として定式化します。タンパク質の3D画像を臨界点のグラフに分割する計算手法を紹介します。ベイズ法と確信度係数法について説明し、臨界点グラフの解析とαヘリックスやβシートなどの意味のある部分構造の特定に使用します。これらの手法を低解像度および中解像度のタンパク質画像に適用した結果を報告します。本研究は、視覚における表現、セグメンテーション、分類へのアプローチ、およびタンパク質構造予測へのトップダウンアプローチに関連しています。
Defining Relative Likelihood in Partially-Ordered Preferential Structures
半順序優先構造における相対尤度の定義
Starting with a likelihood or preference order on worlds, we extend it to a likelihood ordering on sets of worlds in a natural way, and examine the resulting logic. Lewis earlier considered such a notion of relative likelihood in the context of studying counterfactuals, but he assumed a total preference order on worlds. Complications arise when examining partial orders that are not present for total orders. There are subtleties involving the exact approach to lifting the order on worlds to an order on sets of worlds. In addition, the axiomatization of the logic of relative likelihood in the case of partial orders gives insight into the connection between relative likelihood and default reasoning.
世界上の尤度または選好順序から始めて、それを自然な方法で世界集合上の尤度順序へと拡張し、結果として得られる論理を検証します。ルイスは以前、反事実的事象の研究の文脈でこのような相対尤度の概念を検討したが、世界上の全選好順序を仮定していた。全順序には存在しない半順序を検証する際には、複雑な問題が生じる。世界上の順序を世界集合上の順序へと持ち上げる正確なアプローチには、微妙な問題が伴う。さらに、半順序の場合の相対尤度の論理の公理化は、相対尤度とデフォルト推論の関係についての洞察を与える。