Journal of Artificial Intelligence Resarch Vol. 14 (2001)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
Nonapproximability Results for Partially Observable Markov Decision Processes
部分観測マルコフ決定過程における非近似性の結果
We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don’t have guarantees of finding policies within a constant factor or a constant summand of optimal. Here “unlikely” means “unless some complexity classes collapse,” where the collapses considered are P=NP, P=PSPACE, or P=EXP. Until or unless these collapses are shown to hold, any control-policy designer must choose between such performance guarantees and efficient computation.
部分観測マルコフ決定過程のいくつかのバリエーションにおいて、制御方策を求める多項式時間アルゴリズムは、最適値の定数倍または定数和の範囲内で方策を見つけられる可能性は低い、あるいは全く保証がないことを示す。ここで「可能性は低い」とは、「いくつかの複雑性クラスが崩壊しない限り」という意味であり、ここで考慮される崩壊とは、P=NP、P=PSPACE、またはP=EXPです。これらの崩壊が成立することが示されるまでは、あるいは成立しない限り、制御方策設計者は、そのような性能保証と効率的な計算のどちらかを選択しなければならない。
Conflict-Directed Backjumping Revisited
衝突指向バックジャンピングの再考
In recent years, many improvements to backtracking algorithms for solving constraint satisfaction problems have been proposed. The techniques for improving backtracking algorithms can be conveniently classified as look-ahead schemes and look-back schemes. Unfortunately, look-ahead and look-back schemes are not entirely orthogonal as it has been observed empirically that the enhancement of look-ahead techniques is sometimes counterproductive to the effects of look-back techniques. In this paper, we focus on the relationship between the two most important look-ahead techniques—using a variable ordering heuristic and maintaining a level of local consistency during the backtracking search—and the look-back technique of conflict-directed backjumping (CBJ). We show that there exists a “perfect” dynamic variable ordering such that CBJ becomes redundant. We also show theoretically that as the level of local consistency that is maintained in the backtracking search is increased, the less that backjumping will be an improvement. Our theoretical results partially explain why a backtracking algorithm doing more in the look-ahead phase cannot benefit more from the backjumping look-back scheme. Finally, we show empirically that adding CBJ to a backtracking algorithm that maintains generalized arc consistency (GAC), an algorithm that we refer to as GAC-CBJ, can still provide orders of magnitude speedups. Our empirical results contrast with Bessiere and Regin’s conclusion (1996) that CBJ is useless to an algorithm that maintains arc consistency.
近年、制約充足問題を解くためのバックトラッキングアルゴリズムの改良が数多く提案されています。バックトラッキングアルゴリズムの改良手法は、便宜的に先読み手法と後読み手法に分類できます。しかしながら、先読み手法と後読み手法は完全に直交するものではなく、先読み手法の強化が後読み手法の効果を逆効果にしてしまうことが経験的に観察されています。本稿では、最も重要な2つの先読み手法（変数順序付けヒューリスティックの使用と、バックトラッキング探索中の局所的一貫性の維持）と、衝突指向バックジャンピング（CBJ）の後読み手法との関係に焦点を当てる。CBJが不要になるような「完全な」動的変数順序付けが存在することを示す。また、バックトラッキング探索において維持される局所的一貫性のレベルが上昇するにつれて、バックジャンプによる改善効果は低下することを理論的に示す。この理論的結果は、先読みフェーズでより多くの処理を実行するバックトラッキングアルゴリズムが、バックジャンプによるルックバックスキームからより大きな恩恵を受けられない理由を部分的に説明します。最後に、一般化アーク一貫性（GAC）を維持するバックトラッキングアルゴリズムにCBJを追加することで（GAC-CBJと呼ぶ）、桁違いの高速化を実現できることを実証的に示す。この実証結果は、CBJはアーク一貫性を維持するアルゴリズムには役に立たないというBessiereとRegin（1996）の結論とは対照的です。
Conditional Plausibility Measures and Bayesian Networks
条件付き妥当性尺度とベイジアンネットワーク
A general notion of algebraic conditional plausibility measures is defined. Probability measures, ranking functions, possibility measures, and (under the appropriate definitions) sets of probability measures can all be viewed as defining algebraic conditional plausibility measures. It is shown that algebraic conditional plausibility measures can be represented using Bayesian networks.
代数的条件付き妥当性尺度の一般的な概念を定義します。確率尺度、ランキング関数、可能性尺度、そして（適切な定義の下では）確率尺度の集合はすべて、代数的条件付き妥当性尺度を定義するものと見なすことができます。代数的条件付き尤度尺度はベイジアンネットワークを用いて表現できることを示す。
GIB: Imperfect Information in a Computationally Challenging Game
GIB：計算困難なゲームにおける不完全情報
This paper investigates the problems arising in the construction of a program to play the game of contract bridge. These problems include both the difficulty of solving the game’s perfect information variant, and techniques needed to address the fact that bridge is not, in fact, a perfect information game. GIB, the program being described, involves five separate technical advances: partition search, the practical application of Monte Carlo techniques to realistic problems, a focus on achievable sets to solve problems inherent in the Monte Carlo approach, an extension of alpha-beta pruning from total orders to arbitrary distributive lattices, and the use of squeaky wheel optimization to find approximately optimal solutions to cardplay problems. GIB is currently believed to be of approximately expert caliber, and is currently the strongest computer bridge program in the world.
本論文では、コントラクトブリッジのゲームをプレイするプログラムの構築において生じる問題について考察します。これらの問題には、ゲームの完全情報バリアントを解く難しさと、ブリッジが実際には完全情報ゲームではないという事実に対処するために必要な技術の両方が含まれます。本論文で説明するプログラムGIBは、5つの技術的進歩、すなわち、分割探索、モンテカルロ法の現実的な問題への実用的適用、モンテカルロ法に固有の問題を解決するための達成可能集合への焦点、全順序から任意の分配格子へのアルファベータ枝刈りの拡張、そしてカードプレイ問題に対する近似最適解を求めるためのスクイーキーホイール最適化の使用を含む。GIBは現在、ほぼエキスパートレベルであると考えられており、世界最強のコンピュータブリッジプログラムです。
Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes
部分観測マルコフ決定過程における価値反復法の収束の高速化
Partially observable Markov decision processes (POMDPs) have recently become popular among many AI researchers because they serve as a natural model for planning under uncertainty. Value iteration is a well-known algorithm for finding optimal policies for POMDPs. It typically takes a large number of iterations to converge. This paper proposes a method for accelerating the convergence of value iteration. The method has been evaluated on an array of benchmark problems and was found to be very effective: It enabled value iteration to converge after only a few iterations on all the test problems.
部分観測マルコフ決定プロセス(POMDP)は、不確実性下でのプランニングの自然なモデルとして機能するため、最近多くのAI研究者の間で人気が高まっています。価値反復法は、POMDPの最適なポリシーを見つけるためのよく知られたアルゴリズムです。通常、収束するには多数の反復が必要です。本論文では、価値反復法の収束を加速する方法を提案します。この方法は、一連のベンチマーク問題で評価され、非常に効果的であることがわかりました。この方法により、すべてのテスト問題で、わずか数回の反復の後に値の反復が収束することができました。
The FF Planning System: Fast Plan Generation Through Heuristic Search
FF計画システム：ヒューリスティック探索による高速計画生成
We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP’s heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.
FF計画システムで使用されているアルゴリズム手法について説明し、評価します。HSPシステムと同様に、FFは前向き状態空間探索に依存し、削除リストを無視してゴール距離を推定するヒューリスティックを使用します。HSPのヒューリスティックとは異なり、私たちの手法では事実が独立しているとは仮定しません。山登り法と体系的探索を組み合わせた新しい探索戦略を導入し、他の強力なヒューリスティック情報を抽出して探索空間を刈り込む方法を示します。FFは、最近のAIPS-2000プランニング コンペティションで最も成功した自動プランナーでした。私たちはコンペティションの結果をレビューし、他のベンチマーク ドメインのデータを示し、HSPと比較したFFの実行時パフォーマンスの理由を調査します。
Technical Paper Recommendation: A Study in Combining Multiple Information Sources
技術論文推奨：複数の情報源の統合に関する研究
The growing need to manage and exploit the proliferation of online data sources is opening up new opportunities for bringing people closer to the resources they need. For instance, consider a recommendation service through which researchers can receive daily pointers to journal papers in their fields of interest. We survey some of the known approaches to the problem of technical paper recommendation and ask how they can be extended to deal with multiple information sources. More specifically, we focus on a variant of this problem — recommending conference paper submissions to reviewing committee members — which offers us a testbed to try different approaches. Using WHIRL — an information integration system — we are able to implement different recommendation algorithms derived from information retrieval principles. We also use a novel autonomous procedure for gathering reviewer interest information from the Web. We evaluate our approach and compare it to other methods using preference data provided by members of the AAAI-98 conference reviewing committee along with data about the actual submissions.
急増するオンラインデータソースを管理・活用するニーズの高まりは、人々が必要なリソースに近づくための新たな機会を生み出しています。例えば、研究者が関心分野のジャーナル論文を毎日参照できる推薦サービスを考えてみましょう。本稿では、技術論文推薦の問題に対する既存のアプローチをいくつか調査し、それらを複数の情報源に対応させるためにどのように拡張できるかを検討します。より具体的には、この問題の変種である、査読委員会メンバーへの会議論文投稿の推薦に焦点を当てます。これは、様々なアプローチを試すためのテストベッドとなります。情報統合システムであるWHIRLを用いることで、情報検索原理に基づく様々な推薦アルゴリズムを実装することができます。また、Webから査読者の関心情報を収集するための新たな自律的手順も用います。AAAI-98会議査読委員会メンバーから提供された嗜好データと実際の投稿に関するデータを用いて、本アプローチを評価し、他の方法と比較します。
Domain Filtering Consistencies
ドメインフィルタリングの一貫性
Enforcing local consistencies is one of the main features of constraint reasoning. Which level of local consistency should be used when searching for solutions in a constraint network is a basic question. Arc consistency and partial forms of arc consistency have been widely studied, and have been known for sometime through the forward checking or the MAC search algorithms. Until recently, stronger forms of local consistency remained limited to those that change the structure of the constraint graph, and thus, could not be used in practice, especially on large networks. This paper focuses on the local consistencies that are stronger than arc consistency, without changing the structure of the network, i.e., only removing inconsistent values from the domains. In the last five years, several such local consistencies have been proposed by us or by others. We make an overview of all of them, and highlight some relations between them. We compare them both theoretically and experimentally, considering their pruning efficiency and the time required to enforce them.
局所一貫性の強制は、制約推論の主要な特徴の一つです。制約ネットワークにおける解の探索において、どのレベルの局所一貫性を用いるべきかは基本的な問題です。アーク一貫性とアーク一貫性の部分的な形態は広く研究されており、順方向チェックやMAC探索アルゴリズムを通じて以前から知られていました。最近まで、より強力な局所一貫性は制約グラフの構造を変更するものに限られており、特に大規模ネットワークでは実用化できませんでした。本論文では、アーク一貫性よりも強力で、ネットワークの構造を変更せずに、つまりドメインから矛盾する値のみを削除する局所一貫性に焦点を当てます。過去5年間で、このような局所一貫性が我々自身や他の研究者によっていくつか提案されてきました。本論文ではそれらすべてを概観し、それらの関係性を明らかにします。また、枝刈り効率と強制に必要な時間を考慮し、理論的および実験的にそれらを比較します。
What’s in an Attribute? Consequences for the Least Common Subsumer
属性とは何か？最小共通包摂体への影響
Functional relationships between objects, called `attributes’, are of considerable importance in knowledge representation languages, including Description Logics (DLs). A study of the literature indicates that papers have made, often implicitly, different assumptions about the nature of attributes: whether they are always required to have a value, or whether they can be partial functions. The work presented here is the first explicit study of this difference for subclasses of the CLASSIC DL, involving the same-as concept constructor. It is shown that although determining subsumption between concept descriptions has the same complexity (though requiring different algorithms), the story is different in the case of determining the least common subsumer (lcs). For attributes interpreted as partial functions, the lcs exists and can be computed relatively easily; even in this case our results correct and extend three previous papers about the lcs of DLs. In the case where attributes must have a value, the lcs may not exist, and even if it exists it may be of exponential size. Interestingly, it is possible to decide in polynomial time if the lcs exists.
オブジェクト間の機能関係（「属性」と呼ばれる）は、記述論理（DL）を含む知識表現言語において極めて重要です。文献を調査すると、論文ではしばしば暗黙的に、属性の性質について異なる仮定が立てられていることが分かります。属性は常に値を持つ必要があるのか、それとも部分関数になり得るのか、といった仮定です。本研究は、同一概念構成子を含むCLASSIC DLのサブクラスについて、この違いを明示的に検討した初めての研究です。概念記述間の包摂の判定は（異なるアルゴリズムを必要とするものの）同様の複雑さを伴うものの、最小共通包摂体（LCS）の判定の場合は状況が異なることが示されています。部分関数として解釈される属性の場合、LCSは存在し、比較的容易に計算できます。この場合でも、本研究の結果はDLのLCSに関する過去の3つの論文を訂正し、拡張するものです。属性が値を持たなければならない場合、LCSは存在しない可能性があり、たとえ存在したとしても指数関数的な大きさになる可能性があります。興味深いことに、局所一貫性が存在するかどうかを多項式時間で判定することが可能です。
Reasoning within Fuzzy Description Logics
ファジィ記述論理における推論
Description Logics (DLs) are suitable, well-known, logics for managing structured knowledge. They allow reasoning about individuals and well defined concepts, i.e., set of individuals with common properties. The experience in using DLs in applications has shown that in many cases we would like to extend their capabilities. In particular, their use in the context of Multimedia Information Retrieval (MIR) leads to the convincement that such DLs should allow the treatment of the inherent imprecision in multimedia object content representation and retrieval. In this paper we will present a fuzzy extension of ALC, combining Zadeh’s fuzzy logic with a classical DL. In particular, concepts becomes fuzzy and, thus, reasoning about imprecise concepts is supported. We will define its syntax, its semantics, describe its properties and present a constraint propagation calculus for reasoning in it.
記述論理（DL）は、構造化された知識の管理に適した、よく知られた論理です。記述論理は、個体および明確に定義された概念（つまり、共通の特性を持つ個体の集合）についての推論を可能にします。アプリケーションにおけるDLの使用経験から、多くの場合、その機能を拡張したいというニーズがあることがわかりました。特に、マルチメディア情報検索（MIR）の文脈での使用は、マルチメディアオブジェクトコンテンツの表現と検索に内在する不正確さをDLが処理できるはずだという確信に至りました。本稿では、Zadehのファジー論理と従来のDLを組み合わせた、ALCのファジー拡張を提示します。特に、概念がファジーになり、不正確な概念に関する推論がサポートされます。その構文と意味を定義し、その特性を記述し、推論のための制約伝播計算を提示します。
Partial-Order Planning with Concurrent Interacting Actions
同時相互作用アクションを伴う半順序計画
In order to generate plans for agents with multiple actuators, agent teams, or distributed controllers, we must be able to represent and plan using concurrent actions with interacting effects. This has historically been considered a challenging task requiring a temporal planner with the ability to reason explicitly about time. We show that with simple modifications, the STRIPS action representation language can be used to represent interacting actions. Moreover, algorithms for partial-order planning require only small modifications in order to be applied in such multiagent domains. We demonstrate this fact by developing a sound and complete partial-order planner for planning with concurrent interacting actions, POMP, that extends existing partial-order planners in a straightforward way. These results open the way to the use of partial-order planners for the centralized control of cooperative multiagent systems.
複数のアクチュエータ、エージェントチーム、または分散コントローラを持つエージェントの計画を生成するには、相互作用する効果を持つ同時行動を表現し、それらを用いて計画する能力が必要です。これは歴史的に、時間について明示的に推論する能力を持つ時間的プランナーを必要とする困難なタスクと考えられてきました。本研究では、簡単な変更を加えることで、STRIPS行動表現言語を用いて相互作用する行動を表現できることを示します。さらに、半順序プランニングのアルゴリズムは、このようなマルチエージェント領域に適用するためにわずかな変更のみを必要とします。本研究では、既存の半順序プランナーを簡潔に拡張した、同時相互作用行動のプランニングのための健全かつ完全な半順序プランナーPOMPを開発することで、この事実を実証します。これらの結果は、協調型マルチエージェントシステムの集中制御に半順序プランナーを用いる道を開きます。
On Reachability, Relevance, and Resolution in the Planning as Satisfiability Approach
充足可能性としての計画アプローチにおける到達可能性、関連性、および解決について
In recent years, there is a growing awareness of the importance of reachability and relevance-based pruning techniques for planning, but little work specifically targets these techniques. In this paper, we compare the ability of two classes of algorithms to propagate and discover reachability and relevance constraints in classical planning problems. The first class of algorithms operates on SAT encoded planning problems obtained using the linear and Graphplan encoding schemes. It applies unit-propagation and more general resolution steps (involving larger clauses) to these plan encodings. The second class operates at the plan level and contains two families of pruning algorithms: Reachable-k and Relevant-k. Reachable-k provides a coherent description of a number of existing forward pruning techniques used in numerous algorithms, while Relevant-k captures different grades of backward pruning. Our results shed light on the ability of different plan-encoding schemes to propagate information forward and backward and on the relative merit of plan-level and SAT-level pruning methods.
近年、プランニングにおける到達可能性と関連性に基づく枝刈り技術の重要性に対する認識が高まっていますが、これらの技術に特化した研究はほとんどありません。本稿では、古典的なプランニング問題における到達可能性と関連性制約の伝播と発見における2種類のアルゴリズムの能力を比較します。最初のクラスのアルゴリズムは、線形およびGraphplanエンコーディング方式を用いて得られたSATエンコードされたプランニング問題を対象とします。このアルゴリズムは、単位伝播とより一般的な解決ステップ（より大きな節を含む）をこれらのプランエンコーディングに適用します。2つ目のクラスのアルゴリズムはプランレベルで動作し、Reachable-kとRelevant-kという2種類の枝刈りアルゴリズムを含みます。Reachable-kは、数多くのアルゴリズムで使用されている既存の順方向枝刈り技術を首尾一貫して記述する一方、Relevant-kは異なるレベルの逆方向枝刈りを捉えます。本研究の結果は、異なるプランエンコーディング方式が情報を順方向および逆方向に伝播する能力、そしてプランレベルとSATレベルの枝刈り手法の相対的な利点に光を当てます。