Journal of Artificial Intelligence Resarch Vol. 24 (2005)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
mGPT: A Probabilistic Planner Based on Heuristic Search
mGPT：ヒューリスティック探索に基づく確率プランナー
We describe the version of the GPT planner used in the probabilistic track of the 4th International Planning Competition (IPC-4). This version, called mGPT, solves Markov Decision Processes specified in the PPDDL language by extracting and using different classes of lower bounds along with various heuristic-search algorithms. The lower bounds are extracted from deterministic relaxations where the alternative probabilistic effects of an action are mapped into different, independent, deterministic actions. The heuristic-search algorithms use these lower bounds for focusing the updates and delivering a consistent value function over all states reachable from the initial state and the greedy policy.
第4回国際計画コンペティション（IPC-4）の確率トラックで使用されたGPTプランナーのバージョンについて説明します。mGPTと呼ばれるこのバージョンは、PPDDL言語で規定されたマルコフ決定過程を、様々なヒューリスティック探索アルゴリズムと共に、様々なクラスの下限値を抽出して使用することで解決します。下限値は、ある行動の代替確率的影響が異なる独立した決定論的行動にマッピングされる決定論的緩和から抽出されます。ヒューリスティック探索アルゴリズムは、これらの下限値を使用して更新を集中させ、初期状態と貪欲ポリシーから到達可能なすべての状態にわたって一貫した価値関数を提供します。
Optiplan: Unifying IP-based and Graph-based Planning
Optiplan：IPベースとグラフベースのプランニングの統合
The Optiplan planning system is the first integer programming-based planner that successfully participated in the international planning competition. This engineering note describes the architecture of Optiplan and provides the integer programming formulation that enabled it to perform reasonably well in the competition. We also touch upon some recent developments that make integer programming encodings significantly more competitive.
Optiplan計画システムは、国際計画コンペティションに見事に参加した最初の整数計画法ベースのプランナーです。このエンジニアリングノートでは、Optiplanのアーキテクチャについて説明し、コンペティションで良好なパフォーマンスを発揮することを可能にした整数計画法の定式化を示す。また、整数計画法エンコーディングの競争力を大幅に向上させる最近の開発についても触れます。
Ignorability in Statistical and Probabilistic Inference
統計的および確率的推論における無視可能性
When dealing with incomplete data in statistical learning, or incomplete observations in probabilistic inference, one needs to distinguish the fact that a certain event is observed from the fact that the observed event has happened. Since the modeling and computational complexities entailed by maintaining this proper distinction are often prohibitive, one asks for conditions under which it can be safely ignored. Such conditions are given by the missing at random (mar) and coarsened at random (car) assumptions. In this paper we provide an in-depth analysis of several questions relating to mar/car assumptions. Main purpose of our study is to provide criteria by which one may evaluate whether a car assumption is reasonable for a particular data collecting or observational process. This question is complicated by the fact that several distinct versions of mar/car assumptions exist. We therefore first provide an overview over these different versions, in which we highlight the distinction between distributional and coarsening variable induced versions. We show that distributional versions are less restrictive and sufficient for most applications. We then address from two different perspectives the question of when the mar/car assumption is warranted. First we provide a ”static” analysis that characterizes the admissibility of the car assumption in terms of the support structure of the joint probability distribution of complete data and incomplete observations. Here we obtain an equivalence characterization that improves and extends a recent result by Grunwald and Halpern. We then turn to a ”procedural” analysis that characterizes the admissibility of the car assumption in terms of procedural models for the actual data (or observation) generating process. The main result of this analysis is that the stronger coarsened completely at random (ccar) condition is arguably the most reasonable assumption, as it alone corresponds to data coarsening procedures that satisfy a natural robustness property.
統計学習において不完全データ、あるいは確率推論において不完全観測を扱う場合、ある事象が観測されたという事実と、観測された事象が実際に発生したという事実を区別する必要があります。この適切な区別を維持するためのモデリングと計算の複雑さはしばしば法外なものとなるため、これを安全に無視できる条件が求められます。このような条件は、ランダム欠損（mar）仮定とランダム粗大化（car）仮定によって与えられます。本論文では、mar/car仮定に関するいくつかの疑問について詳細な分析を行います。本研究の主な目的は、特定のデータ収集プロセスまたは観測プロセスにおいてcar仮定が妥当かどうかを評価する基準を提供することです。この問題は、mar/car仮定に複数の異なるバージョンが存在するという事実によって複雑化しています。そこでまず、これらの異なるバージョンの概要を示し、分布変数誘導バージョンと粗大化変数誘導バージョンの区別を明確にします。分布変数誘導バージョンは制約が少なく、ほとんどのアプリケーションにおいて十分であることを示します。次に、mar/car仮定がどのような場合に正当化されるのかという問題を、2つの異なる観点から考察します。まず、完全データと不完全観測値の結合確率分布の支持構造の観点から、car仮定の許容性を特徴付ける「静的」解析を行う。ここでは、GrunwaldとHalpernによる最近の結果を改良・拡張する同値性解析を行う。次に、実際のデータ（または観測値）生成プロセスの手続きモデルの観点から、car仮定の許容性を特徴付ける「手続き的」解析を行う。この解析の主な結果は、より強い粗大化完全ランダム（ccar）条件が、自然な堅牢性特性を満たすデータ粗大化手順に対応する唯一の条件であるため、おそらく最も合理的な仮定であるということです。
The First Probabilistic Track of the International Planning Competition
国際プランニングコンペティション初の確率的トラック
The 2004 International Planning Competition, IPC-4, included a probabilistic planning track for the first time. We describe the new domain specification language we created for the track, our evaluation methodology, the competition domains we developed, and the results of the participating teams.
2004年の国際計画コンペティションIPC-4では、初めて確率計画トラックが設けられました。本稿では、このトラックのために作成した新しいドメイン仕様言語、評価方法、開発した競技ドメイン、そして参加チームの結果について説明します。
Risk-Sensitive Reinforcement Learning Applied to Control under Constraints
制約下制御へのリスク感受性強化学習の適用
In this paper, we consider Markov Decision Processes (MDPs) with error states. Error states are those states entering which is undesirable or dangerous. We define the risk with respect to a policy as the probability of entering such a state when the policy is pursued. We consider the problem of finding good policies whose risk is smaller than some user-specified threshold, and formalize it as a constrained MDP with two criteria. The first criterion corresponds to the value function originally given. We will show that the risk can be formulated as a second criterion function based on a cumulative return, whose definition is independent of the original value function. We present a model free, heuristic reinforcement learning algorithm that aims at finding good deterministic policies. It is based on weighting the original value function and the risk. The weight parameter is adapted in order to find a feasible solution for the constrained problem that has a good performance with respect to the value function. The algorithm was successfully applied to the control of a feed tank with stochastic inflows that lies upstream of a distillation column. This control task was originally formulated as an optimal control problem with chance constraints, and it was solved under certain assumptions on the model to obtain an optimal solution. The power of our learning algorithm is that it can be used even when some of these restrictive assumptions are relaxed.
本稿では、エラー状態を持つマルコフ決定過程（MDP）を検討します。エラー状態とは、望ましくない、あるいは危険な状態に入ることです。ポリシーに関するリスクとは、ポリシーが追求された際にそのような状態に入る確率と定義します。リスクがユーザー指定の閾値よりも小さい優れたポリシーを見つける問題を考察し、2つの基準を持つ制約付きMDPとして定式化します。最初の基準は、元々与えられた価値関数に対応します。リスクは、定義が元の価値関数に依存しない累積収益に基づく2番目の基準関数として定式化できることを示します。優れた決定論的ポリシーを見つけることを目的とした、モデルフリーのヒューリスティック強化学習アルゴリズムを紹介します。このアルゴリズムは、元の価値関数とリスクに重み付けをすることで実現されます。重みパラメータは、価値関数に関して良好な性能を示す制約付き問題の実行可能な解を見つけるために調整されます。このアルゴリズムは、蒸留塔の上流に位置する、確率的な流入を伴う供給タンクの制御にうまく適用されました。この制御タスクは、もともと確率制約を伴う最適制御問題として定式化され、モデルに関する特定の仮定の下で最適解を得るために解かれました。私たちの学習アルゴリズムの強みは、これらの制約的な仮定の一部を緩和した場合でも使用できることです。
Probabilistic Hybrid Action Models for Predicting Concurrent Percept-driven Robot Behavior
同時知覚駆動型ロボット行動を予測するための確率的ハイブリッド行動モデル
This article develops Probabilistic Hybrid Action Models (PHAMs), a realistic causal model for predicting the behavior generated by modern percept-driven robot plans. PHAMs represent aspects of robot behavior that cannot be represented by most action models used in AI planning: the temporal structure of continuous control processes, their non-deterministic effects, several modes of their interferences, and the achievement of triggering conditions in closed-loop robot plans. The main contributions of this article are: (1) PHAMs, a model of concurrent percept-driven behavior, its formalization, and proofs that the model generates probably, qualitatively accurate predictions; and (2) a resource-efficient inference method for PHAMs based on sampling projections from probabilistic action models and state descriptions. We show how PHAMs can be applied to planning the course of action of an autonomous robot office courier based on analytical and experimental results.
本稿では、現代の知覚駆動型ロボット計画によって生成される行動を予測するための現実的な因果モデルである確率的ハイブリッド行動モデル（PHAM）を開発します。PHAMは、AI計画で使用されるほとんどの行動モデルでは表現できないロボット行動の側面、すなわち連続制御プロセスの時間的構造、それらの非決定論的影響、それらの干渉のいくつかのモード、および閉ループロボット計画におけるトリガー条件の達成を表現します。本稿の主な貢献は、（1）同時知覚駆動型行動モデルであるPHAM、その形式化、およびモデルがおそらく定性的に正確な予測を生成することの証明、および（2）確率行動モデルと状態記述からのサンプリング投影に基づく、PHAMのためのリソース効率の高い推論手法です。分析結果と実験結果に基づいて、PHAMを自律型オフィス宅配ロボットの行動計画にどのように適用できるかを示す。
Relational Dynamic Bayesian Networks
関係動的ベイジアンネットワーク
Stochastic processes that involve the creation of objects and relations over time are widespread, but relatively poorly studied. For example, accurate fault diagnosis in factory assembly processes requires inferring the probabilities of erroneous assembly operations, but doing this efficiently and accurately is difficult. Modeled as dynamic Bayesian networks, these processes have discrete variables with very large domains and extremely high dimensionality. In this paper, we introduce relational dynamic Bayesian networks (RDBNs), which are an extension of dynamic Bayesian networks (DBNs) to first-order logic. RDBNs are a generalization of dynamic probabilistic relational models (DPRMs), which we had proposed in our previous work to model dynamic uncertain domains. We first extend the Rao-Blackwellised particle filtering described in our earlier work to RDBNs. Next, we lift the assumptions associated with Rao-Blackwellization in RDBNs and propose two new forms of particle filtering. The first one uses abstraction hierarchies over the predicates to smooth the particle filter’s estimates. The second employs kernel density estimation with a kernel function specifically designed for relational domains. Experiments show these two methods greatly outperform standard particle filtering on the task of assembly plan execution monitoring.
時間経過に伴うオブジェクトと関係の生成を伴う確率過程は広く普及しているが、比較的研究が不足しています。例えば、工場の組立工程における正確な故障診断には、誤った組立作業の確率を推論する必要があるが、これを効率的かつ正確に行うことは困難です。動的ベイジアンネットワークとしてモデル化すると、これらの過程は非常に大きな領域と極めて高い次元を持つ離散変数を持つ。本稿では、動的ベイジアンネットワーク（DBN）を一階述語論理に拡張した関係動的ベイジアンネットワーク（RDBN）を紹介します。RDBNは、動的確率関係モデル（DPRM）の一般化であり、我々は以前の研究で動的な不確実性領域をモデル化するためにDPRMを提案した。まず、以前の研究で述べたRao-Blackwell化粒子フィルタリングをRDBNに拡張します。次に、RDBNにおけるRao-Blackwell化に関連する仮定を取り除き、2つの新しい形式の粒子フィルタリングを提案します。1つ目は、述語の抽象化階層を用いて粒子フィルタの推定値を平滑化します。2つ目は、関係領域向けに特別に設計されたカーネル関数を用いたカーネル密度推定を用います。実験では、これら2つの手法が、組立計画実行監視タスクにおいて標準的な粒子フィルタリングを大幅に上回る性能を示すことが示されました。
Where ‘Ignoring Delete Lists’ Works: Local Search Topology in Planning Benchmarks
「削除リストを無視する」ことが機能する場所：プランニングベンチマークにおける局所探索トポロジー
Between 1998 and 2004, the planning community has seen vast progress in terms of the sizes of benchmark examples that domain-independent planners can tackle successfully. The key technique behind this progress is the use of heuristic functions based on relaxing the planning task at hand, where the relaxation is to assume that all delete lists are empty. The unprecedented success of such methods, in many commonly used benchmark examples, calls for an understanding of what classes of domains these methods are well suited for. In the investigation at hand, we derive a formal background to such an understanding. We perform a case study covering a range of 30 commonly used STRIPS and ADL benchmark domains, including all examples used in the first four international planning competitions. We *prove* connections between domain structure and local search topology — heuristic cost surface properties — under an idealized version of the heuristic functions used in modern planners. The idealized heuristic function is called h^+, and differs from the practically used functions in that it returns the length of an *optimal* relaxed plan, which is NP-hard to compute. We identify several key characteristics of the topology under h^+, concerning the existence/non-existence of unrecognized dead ends, as well as the existence/non-existence of constant upper bounds on the difficulty of escaping local minima and benches. These distinctions divide the (set of all) planning domains into a taxonomy of classes of varying h^+ topology. As it turns out, many of the 30 investigated domains lie in classes with a relatively easy topology. Most particularly, 12 of the domains lie in classes where FF’s search algorithm, provided with h^+, is a polynomial solving mechanism. We also present results relating h^+ to its approximation as implemented in FF. The behavior regarding dead ends is provably the same. We summarize the results of an empirical investigation showing that, in many domains, the topological qualities of h^+ are largely inherited by the approximation. The overall investigation gives a rare example of a successful analysis of the connections between typical-case problem structure, and search performance. The theoretical investigation also gives hints on how the topological phenomena might be automatically recognizable by domain analysis techniques. We outline some preliminary steps we made into that direction.
1998年から2004年にかけて、計画コミュニティでは、ドメイン独立型プランナーが適切に処理できるベンチマーク例のサイズに関して、大きな進歩が見られました。この進歩の背後にある主要な手法は、手元の計画タスクを緩和することに基づくヒューリスティック関数の使用です。この緩和では、すべての削除リストが空であると想定します。多くの一般的に使用されるベンチマーク例でこのような方法が前例のない成功を収めたことで、これらの方法がどのドメインのクラスに適しているかを理解する必要があります。今回の調査では、このような理解の正式な背景を導き出します。私たちは、最初の4つの国際計画コンテストで使用されたすべての例を含む、一般的に使用される30のSTRIPSおよびADLベンチマーク ドメインを対象とするケース スタディを実行します。現代のプランナーで使用されるヒューリスティック関数の理想化されたバージョンの下で、ドメイン構造と局所探索トポロジー(ヒューリスティック コスト曲面特性)の関係を*証明*します。理想的なヒューリスティック関数はh^+と呼ばれ、実際に用いられる関数とは異なり、*最適*な緩和計画の長さを返す。これはNP困難であり、計算が困難です。h^+における位相の重要な特性として、認識されない行き止まりの有無、および局所最小値とベンチからの脱出難易度の上限値の有無が挙げられます。これらの区別により、（すべての）計画領域は、様々なh^+位相を持つクラスの分類に分類されます。結果として、調査した30の領域の多くは、比較的容易な位相を持つクラスに属します。特に、12の領域は、h^+を前提とするFFの探索アルゴリズムが多項式解法となるクラスに属します。また、h^+とFFに実装されたその近似値との関連を示す。行き止まりに関する挙動は、証明上は同一です。多くの領域において、h^+の位相的性質は近似によってほぼ継承されることを示す実証的調査の結果を要約します。全体的な調査は、典型的なケースの問題構造と探索性能の関係を分析することに成功した稀有な例を提供します。理論的調査はまた、領域分析技術によって位相的現象がどのように自動的に認識されるかについてのヒントを与える。我々はその方向に向けて行ったいくつかの予備的ステップを概説します。
Binary Encodings of Non-binary Constraint Satisfaction Problems: Algorithms and Experimental Results
非バイナリ制約充足問題のバイナリ符号化：アルゴリズムと実験結果
A non-binary Constraint Satisfaction Problem (CSP) can be solved directly using extended versions of binary techniques. Alternatively, the non-binary problem can be translated into an equivalent binary one. In this case, it is generally accepted that the translated problem can be solved by applying well-established techniques for binary CSPs. In this paper we evaluate the applicability of the latter approach. We demonstrate that the use of standard techniques for binary CSPs in the encodings of non-binary problems is problematic and results in models that are very rarely competitive with the non-binary representation. To overcome this, we propose specialized arc consistency and search algorithms for binary encodings, and we evaluate them theoretically and empirically. We consider three binary representations; the hidden variable encoding, the dual encoding, and the double encoding. Theoretical and empirical results show that, for certain classes of non-binary constraints, binary encodings are a competitive option, and in many cases, a better one than the non-binary representation.
非バイナリ制約充足問題（CSP）は、バイナリ表現の拡張版を用いて直接解くことができます。あるいは、非バイナリ問題を等価なバイナリ問題に翻訳することも可能です。この場合、翻訳された問題はバイナリCSP用の確立された手法を適用することで解決できることが一般的に認められています。本論文では、後者のアプローチの適用可能性を評価します。非バイナリ問題の符号化においてバイナリCSPの標準的な手法を用いることは問題が多く、結果として得られるモデルが非バイナリ表現と競合することは極めて稀であることを示します。この問題を解決するため、バイナリ表現に特化した弧整合性および探索アルゴリズムを提案し、理論的および実証的に評価します。ここでは、隠れ変数符号化、双対符号化、および二重符号化の3つのバイナリ表現を検討します。理論的および実証的結果は、特定のクラスの非バイナリ制約に対して、バイナリ符号化が競合可能な選択肢であり、多くの場合、非バイナリ表現よりも優れた選択肢であることを示しています。
Hiding Satisfying Assignments: Two are Better than One
充足割り当ての隠蔽：2つは1つより優れている
The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-SAT formulas whose clauses are chosen uniformly from among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner tend to be relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, for a number of different algorithms, A acts as a stronger and stronger attractor as the formula’s density increases. Motivated by recent results on the geometry of the space of satisfying truth assignments of random k-SAT and NAE-k-SAT formulas, we introduce a simple twist on this basic model, which appears to dramatically increase its hardness. Namely, in addition to forbidding the clauses violated by the hidden assignment A, we also forbid the clauses violated by its complement, so that both A and compliment of A are satisfying. It appears that under this “symmetrization” the effects of the two attractors largely cancel out, making it much harder for algorithms to find any truth assignment. We give theoretical and experimental evidence supporting this assertion.
不完全充足可能性ソルバーの評価は、困難な充足可能インスタンスの可用性に大きく依存します。そのようなインスタンスの妥当なソースとしては、ランダムに選択された真理値割当Aを満たすすべての節の中から一様に節が選択されたランダムk-SAT式が挙げられます。残念ながら、このように生成されたインスタンスは比較的容易であり、実用的なヒューリスティックによって効率的に解くことができる傾向があります。大まかに言えば、様々なアルゴリズムにおいて、式の密度が増加するにつれて、Aはより強いアトラクターとして作用します。ランダムk-SAT式およびNAE-k-SAT式の充足真理値割当空間の幾何学に関する最近の研究結果に着目し、我々はこの基本モデルに単純な工夫を加えることで、モデルの困難性を劇的に向上させるようにします。すなわち、隠れた割当Aによって違反する節を禁止することに加えて、その補節によって違反する節も禁止することで、Aと補節Aの両方が充足可能となります。この「対称化」の下では、2つのアトラクターの効果はほぼ打ち消され、アルゴリズムによる真理値の割り当てがはるかに困難になるようです。この主張を裏付ける理論的および実験的証拠を示します。
Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators
マクロFF：自動学習マクロ演算子を用いたAIプランニングの改善
Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present and compare two automated methods that learn relevant information from previous experience in a domain and use it to solve new problem instances. Our methods share a common four-step strategy. First, a domain is analyzed and structural information is extracted, then macro-operators are generated based on the previously discovered structure. A filtering and ranking procedure selects the most useful macro-operators. Finally, the selected macros are used to speed up future searches. We have successfully used such an approach in the fourth international planning competition IPC-4. Our system, Macro-FF, extends Hoffmann’s state-of-the-art planner FF 2.3 with support for two kinds of macro-operators, and with engineering enhancements. We demonstrate the effectiveness of our ideas on benchmarks from international planning competitions. Our results indicate a large reduction in search effort in those complex domains where structural information can be inferred.
AIプランニングにおける近年の進歩にもかかわらず、多くのベンチマークは現在のプランナーにとって依然として課題となっています。多くの分野において、初期のPDDL定式化に明示的にエンコードされていないドメイン構造に関する情報を発見し、活用することで、プランナーの性能を大幅に向上させることができます。本稿では、ある分野における過去の経験から関連情報を学習し、それを用いて新たな問題インスタンスを解く2つの自動化手法を提示し、比較します。これらの手法は、共通の4段階の戦略を採用しています。まず、ドメインを分析し、構造情報を抽出します。次に、発見された構造に基づいてマクロ演算子を生成します。フィルタリングとランキングの手順により、最も有用なマクロ演算子が選択されます。最後に、選択されたマクロ演算子は、将来の探索を高速化するために用いられます。私たちは、このアプローチを第4回国際プランニングコンペティションIPC-4で成功裏に採用しました。私たちのシステムであるMacro-FFは、Hoffmannの最先端のプランナーFF 2.3を拡張し、2種類のマクロ演算子のサポートとエンジニアリングの強化を実現しています。私たちは、国際プランニングコンペティションのベンチマークにおいて、私たちのアイデアの有効性を実証します。我々の研究結果は、構造情報が推論可能な複雑な領域において、探索労力が大幅に削減されることを示しています。
The Deterministic Part of IPC-4: An Overview
IPC-4 の決定論的部分：概要
We provide an overview of the organization and results of the deterministic part of the 4th International Planning Competition, i.e., of the part concerned with evaluating systems doing deterministic planning. IPC-4 attracted even more competing systems than its already large predecessors, and the competition event was revised in several important respects. After giving an introduction to the IPC, we briefly explain the main differences between the deterministic part of IPC-4 and its predecessors. We then introduce formally the language used, called PDDL2.2 that extends PDDL2.1 by derived predicates and timed initial literals. We list the competing systems and overview the results of the competition. The entire set of data is far too large to be presented in full. We provide a detailed summary; the complete data is available in an online appendix. We explain how we awarded the competition prizes.
第4回国際計画コンペティションの決定論的部分、すなわち決定論的計画を行うシステムの評価に関する部分の構成と結果の概要を示します。IPC-4には、すでに大規模であった前回のコンペティションよりもさらに多くの競合システムが参加し、コンペティション イベントはいくつかの重要な点で改訂されました。IPCの概要を説明した後、IPC-4の決定論的部分と前回の主な違いについて簡単に説明します。次に、PDDL2.1を導出述語と時間指定初期リテラルによって拡張したPDDL2.2と呼ばれる言語を正式に紹介します。競合システムをリストし、コンペティションの結果を概観します。データ セット全体が大きすぎてすべてを提示することはできません。詳細な概要を示します。完全なデータはオンラインの付録で入手できます。コンペティションの賞の授与方法について説明します。
A Framework for Sequential Planning in Multi-Agent Settings
マルチエージェント環境における逐次計画のためのフレームワーク
This paper extends the framework of partially observable Markov decision processes (POMDPs) to multi-agent settings by incorporating the notion of agent models into the state space. Agents maintain beliefs over physical states of the environment and over models of other agents, and they use Bayesian updates to maintain their beliefs over time. The solutions map belief states to actions. Models of other agents may include their belief states and are related to agent types considered in games of incomplete information. We express the agents’ autonomy by postulating that their models are not directly manipulable or observable by other agents. We show that important properties of POMDPs, such as convergence of value iteration, the rate of convergence, and piece-wise linearity and convexity of the value functions carry over to our framework. Our approach complements a more traditional approach to interactive settings which uses Nash equilibria as a solution paradigm. We seek to avoid some of the drawbacks of equilibria which may be non-unique and do not capture off-equilibrium behaviors. We do so at the cost of having to represent, process and continuously revise models of other agents. Since the agent’s beliefs may be arbitrarily nested, the optimal solutions to decision making problems are only asymptotically computable. However, approximate belief updates and approximately optimal plans are computable. We illustrate our framework using a simple application domain, and we show examples of belief updates and value functions.
本論文は、エージェントモデルの概念を状態空間に組み込むことで、部分観測マルコフ決定過程（POMDP）の枠組みをマルチエージェント設定に拡張します。エージェントは、環境の物理状態と他のエージェントのモデルに関する信念を維持し、ベイズ更新を用いて時間経過に伴って信念を維持します。この解は、信念状態を行動にマッピングします。他のエージェントのモデルには、自身の信念状態が含まれる場合があり、不完全情報ゲームで想定されるエージェントの種類と関連しています。エージェントの自律性は、エージェントのモデルが他のエージェントによって直接操作または観測できないという仮定によって表現されます。POMDPの重要な特性、例えば価値反復の収束性、収束速度、価値関数の区分線形性および凸性などは、我々の枠組みにも引き継がれることを示します。我々のアプローチは、ナッシュ均衡を解法パラダイムとして用いる、インタラクティブな設定に対するより伝統的なアプローチを補完するものです。我々は、均衡が一意ではない可能性があり、均衡から外れた行動を捉えられないという欠点のいくつかを回避することを目指しています。しかし、他のエージェントのモデルを表現、処理、そして継続的に修正する必要があるという代償を払うことになります。エージェントの信念は任意に入れ子になっている可能性があるため、意思決定問題に対する最適解は漸近的にしか計算できない。しかし、近似的な信念更新と近似的な最適計画は計算可能です。我々は、単純な適用領域を用いて我々のフレームワークを説明し、信念更新と価値関数の例を示す。
Reasoning about Action: An Argumentation – Theoretic Approach
行動に関する推論：議論 – 理論的アプローチ
We present a uniform non-monotonic solution to the problems of reasoning about action on the basis of an argumentation-theoretic approach. Our theory is provably correct relative to a sensible minimisation policy introduced on top of a temporal propositional logic. Sophisticated problem domains can be formalised in our framework. As much attention of researchers in the field has been paid to the traditional and basic problems in reasoning about actions such as the frame, the qualification and the ramification problems, approaches to these problems within our formalisation lie at heart of the expositions presented in this paper.
私たちは、議論理論的アプローチに基づき、行動に関する推論の問題に対する均一な非単調解を提示します。私たちの理論は、時相命題論理の上に導入された合理的な最小化ポリシーと比較して、証明可能に正しいです。高度な問題領域も私たちのフレームワークで形式化できます。この分野の研究者は、フレーム問題、資格問題、分岐問題といった、行動に関する推論における伝統的かつ基本的な問題に多くの関心を寄せてきましたが、本論文で提示する説明の中核は、これらの問題に対する我々の形式化におけるアプローチにあります。
Cooperative Information Sharing to Improve Distributed Learning in Multi-Agent Systems
マルチエージェントシステムにおける分散学習を改善するための協力的情報共有
Effective coordination of agents’ actions in partially-observable domains is a major challenge of multi-agent systems research. To address this, many researchers have developed techniques that allow the agents to make decisions based on estimates of the states and actions of other agents that are typically learnt using some form of machine learning algorithm. Nevertheless, many of these approaches fail to provide an actual means by which the necessary information is made available so that the estimates can be learnt. To this end, we argue that cooperative communication of state information between agents is one such mechanism. However, in a dynamically changing environment, the accuracy and timeliness of this communicated information determine the fidelity of the learned estimates and the usefulness of the actions taken based on these. Given this, we propose a novel information-sharing protocol, post-task-completion sharing, for the distribution of state information. We then show, through a formal analysis, the improvement in the quality of estimates produced using our strategy over the widely used protocol of sharing information between nearest neighbours. Moreover, communication heuristics designed around our information-sharing principle are subjected to empirical evaluation along with other benchmark strategies (including Littman’s Q-routing and Stone’s TPOT-RL) in a simulated call-routing application. These studies, conducted across a range of environmental settings, show that, compared to the different benchmarks used, our strategy generates an improvement of up to 60% in the call connection rate; of more than 1000% in the ability to connect long-distance calls; and incurs as low as 0.25 of the message overhead.
部分観測領域におけるエージェントの行動の効果的な調整は、マルチエージェントシステム研究における主要な課題です。この課題に対処するため、多くの研究者が、他のエージェントの状態と行動の推定値（通常は何らかの機械学習アルゴリズムを用いて学習）に基づいてエージェントが意思決定を行う技術を開発してきました。しかしながら、これらのアプローチの多くは、推定値を学習するために必要な情報を提供するための具体的な手段を提供していません。そこで、エージェント間の状態情報の協調的な通信がそのようなメカニズムの一つであると主張します。しかしながら、動的に変化する環境においては、通信される情報の正確性と適時性が、学習された推定値の忠実度と、それに基づいて取られる行動の有用性を決定します。この点を踏まえ、状態情報を配布するための新しい情報共有プロトコル、タスク完了後共有を提案します。そして、形式的な分析を通して、本戦略を用いることで、最近傍間で情報を共有するという広く用いられているプロトコルと比較して、推定値の品質が向上することを示します。さらに、情報共有原理に基づいて設計されたコミュニケーションヒューリスティックは、他のベンチマーク戦略（LittmanのQルーティングやStoneのTPOT-RLなど）と共に、シミュレートされたコールルーティングアプリケーションにおいて実証的に評価されました。様々な環境設定で実施されたこれらの研究は、使用された様々なベンチマークと比較して、私たちの戦略はコール接続率を最大60%、長距離通話の接続能力を1000%以上向上させ、メッセージオーバーヘッドをわずか0.25%に抑えることを示しています。
Pure Nash Equilibria: Hard and Easy Games
純粋ナッシュ均衡：難しいゲームと簡単なゲーム
We investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is SigmaP2-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each player’s payoff depends on moves of other players. We say that a game has small neighborhood if the utility function for each player depends only on (the actions of) a logarithmically small number of other players. The dependency structure of a game G can be expressed by a graph DG(G) or by a hypergraph H(G). By relating Nash equilibrium problems to constraint satisfaction problems (CSPs), we show that if G has small neighborhood and if H(G) has bounded hypertree width (or if DG(G) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class NC2 of highly parallelizable problems.
戦略ゲームの純粋ナッシュ均衡に関連する計算量の問題を調査します。非常に制限の厳しい設定であっても、ゲームが純粋ナッシュ均衡を持つかどうかを判断することはNP困難である一方、ゲームが強いナッシュ均衡を持つかどうかを判断することはSigmaP2完全であることを示す。次に、計算量を低減する実用的に関連する制約を研究します。特に、各プレイヤーの利得が他のプレイヤーの動きによってどのように左右されるかに関する量的・質的制約に着目しています。各プレイヤーの効用関数が他のプレイヤーの（行動の）対数的に少ない数にのみ依存する場合、ゲームは小さな近傍を持つといいます。ゲームGの依存構造は、グラフDG(G)またはハイパーグラフH(G)で表現できます。ナッシュ均衡問題を制約充足問題(CSP)に関連付けることで、Gが小さな近傍を持ち、H(G)がハイパーツリー幅に制限がある場合(またはDG(G)がツリー幅に制限がある場合)、純粋なナッシュ均衡とパレート均衡を多項式時間で見つけることが可能であることを示します。ゲームがグラフィカルな場合、これらの問題はLOGCFL完全であり、したがって高度に並列化可能な問題のクラスNC2に属します。
Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms
オンライン学習アルゴリズムにおけるブールカーネルの効率性と収束性
The paper studies machine learning problems where each example is described using a set of Boolean features and where hypotheses are represented by linear threshold elements. One method of increasing the expressiveness of learned hypotheses in this context is to expand the feature set to include conjunctions of basic features. This can be done explicitly or where possible by using a kernel function. Focusing on the well known Perceptron and Winnow algorithms, the paper demonstrates a tradeoff between the computational efficiency with which the algorithm can be run over the expanded feature space and the generalization ability of the corresponding learning algorithm. We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Perceptron algorithm over a feature space of exponentially many conjunctions; however we also show that using such kernels, the Perceptron algorithm can provably make an exponential number of mistakes even when learning simple functions. We then consider the question of whether kernel functions can analogously be used to run the multiplicative-update Winnow algorithm over an expanded feature space of exponentially many conjunctions. Known upper bounds imply that the Winnow algorithm can learn Disjunctive Normal Form (DNF) formulae with a polynomial mistake bound in this setting. However, we prove that it is computationally hard to simulate Winnow’s behavior for learning DNF over such a feature set. This implies that the kernel functions which correspond to running Winnow for this problem are not efficiently computable, and that there is no general construction that can run Winnow with kernels.
本論文では、各例がブール型特徴量の集合を用いて記述され、仮説が線形閾値要素で表される機械学習問題を対象とします。この文脈において学習された仮説の表現力を高める一つの方法は、特徴量セットを拡張して基本特徴量の連言を含めることです。これは明示的に行うことも、可能な場合はカーネル関数を用いて行うこともできます。本論文では、よく知られているパーセプトロンアルゴリズムとウィノウアルゴリズムに焦点を当て、拡張された特徴空間上でアルゴリズムを実行する際の計算効率と、対応する学習アルゴリズムの一般化能力との間のトレードオフを示す。まず、限定された形式の連言またはすべての連言を捕捉する複数のカーネル関数について説明します。これらのカーネルを用いることで、指数関数的に多数の連言を含む特徴空間上でパーセプトロンアルゴリズムを効率的に実行できることを示す。しかし同時に、このようなカーネルを用いると、パーセプトロンアルゴリズムは単純な関数を学習する場合でも、指数関数的な数の誤りを犯す可能性があることも示す。次に、カーネル関数を用いて、指数関数的に多数の連言を含む拡張された特徴空間上で乗法更新Winnowアルゴリズムを実行する際に、同様に使用できるかどうかを考察します。既知の上限は、Winnowアルゴリズムがこの設定において多項式誤り境界を持つ選言正規形（DNF）式を学習できることを意味します。しかし、そのような特徴セット上でDNFを学習するためのWinnowの挙動をシミュレートすることは計算的に困難であることを証明した。これは、この問題に対してWinnowを実行することに対応するカーネル関数が効率的に計算可能ではなく、カーネルを用いてWinnowを実行できる一般的な構成が存在しないことを意味します。
Learning Concept Hierarchies from Text Corpora using Formal Concept Analysis
形式概念分析を用いたテキストコーパスからの概念階層の学習
We present a novel approach to the automatic acquisition of taxonomies or concept hierarchies from a text corpus. The approach is based on Formal Concept Analysis (FCA), a method mainly used for the analysis of data, i.e. for investigating and processing explicitly given information. We follow Harris’ distributional hypothesis and model the context of a certain term as a vector representing syntactic dependencies which are automatically acquired from the text corpus with a linguistic parser. On the basis of this context information, FCA produces a lattice that we convert into a special kind of partial order constituting a concept hierarchy. The approach is evaluated by comparing the resulting concept hierarchies with hand-crafted taxonomies for two domains: tourism and finance. We also directly compare our approach with hierarchical agglomerative clustering as well as with Bi-Section-KMeans as an instance of a divisive clustering algorithm. Furthermore, we investigate the impact of using different measures weighting the contribution of each attribute as well as of applying a particular smoothing technique to cope with data sparseness.
テキストコーパスからタクソノミーまたは概念階層を自動的に取得する新しいアプローチを紹介します。このアプローチは、主にデータ分析、つまり明示的に与えられた情報の調査と処理に用いられる手法である形式概念分析（FCA）に基づいています。ハリスの分布仮説に従い、特定の用語のコンテキストを、言語パーサーによってテキストコーパスから自動的に取得される統語的依存関係を表すベクトルとしてモデル化します。このコンテキスト情報に基づいて、FCAは概念階層を構成する特殊な半順序に変換する格子を生成します。このアプローチは、結果として得られる概念階層を、観光と金融という2つのドメインについて手動で作成したタクソノミーと比較することで評価されます。また、このアプローチを階層的凝集型クラスタリングや、分割クラスタリングアルゴリズムの例としてBi-Section-KMeansと直接比較します。さらに、各属性の寄与を重み付けする異なる尺度を用いること、およびデータのスパース性に対処するために特定の平滑化手法を適用することの影響についても調査します。
Integrating Learning from Examples into the Search for Diagnostic Policies
例からの学習を診断方策の探索に統合する
This paper studies the problem of learning diagnostic policies from training examples. A diagnostic policy is a complete description of the decision-making actions of a diagnostician (i.e., tests followed by a diagnostic decision) for all possible combinations of test results. An optimal diagnostic policy is one that minimizes the expected total cost, which is the sum of measurement costs and misdiagnosis costs. In most diagnostic settings, there is a tradeoff between these two kinds of costs. This paper formalizes diagnostic decision making as a Markov Decision Process (MDP). The paper introduces a new family of systematic search algorithms based on the AO* algorithm to solve this MDP. To make AO* efficient, the paper describes an admissible heuristic that enables AO* to prune large parts of the search space. The paper also introduces several greedy algorithms including some improvements over previously-published methods. The paper then addresses the question of learning diagnostic policies from examples. When the probabilities of diseases and test results are computed from training data, there is a great danger of overfitting. To reduce overfitting, regularizers are integrated into the search algorithms. Finally, the paper compares the proposed methods on five benchmark diagnostic data sets. The studies show that in most cases the systematic search methods produce better diagnostic policies than the greedy methods. In addition, the studies show that for training sets of realistic size, the systematic search algorithms are practical on today’s desktop computers.
本論文では、トレーニング例から診断ポリシーを学習する問題について検討します。診断ポリシーとは、あらゆる可能な検査結果の組み合わせに対する診断医の意思決定行動（つまり、検査とそれに続く診断決定）の完全な記述です。最適な診断ポリシーとは、測定コストと誤診コストの合計である期待総コストを最小化するポリシーです。ほとんどの診断設定では、これら2種類のコストの間にトレードオフが存在します。本論文では、診断意思決定をマルコフ決定過程（MDP）として定式化します。本論文では、このMDPを解くためのAO*アルゴリズムに基づく新しい体系的探索アルゴリズム群を紹介します。AO*を効率的にするために、本論文では、AO*が探索空間の大部分を刈り込むことを可能にする許容可能なヒューリスティックについて述べる。また、本論文では、従来手法を改良した複数の貪欲アルゴリズムも紹介します。次に、例から診断方針を学習するという問題について考察します。疾患の確率と検査結果をトレーニングデータから計算する場合、過学習の大きな危険性があります。過学習を軽減するために、探索アルゴリズムに正則化子を組み込む。最後に、本論文では、5つのベンチマーク診断データセットを用いて提案手法を比較します。これらの研究は、ほとんどの場合、体系的探索法が貪欲法よりも優れた診断方針を生成することを示しています。さらに、現実的なサイズのトレーニングデータに対しては、体系的探索アルゴリズムが今日のデスクトップコンピュータで実用的であることを示しています。
Linking Search Space Structure, Run-Time Dynamics, and Problem Difficulty: A Step Toward Demystifying Tabu Search
探索空間構造、実行時ダイナミクス、問題の難易度の関連付け：タブー探索の解明に向けた一歩
Tabu search is one of the most effective heuristics for locating high-quality solutions to a diverse array of NP-hard combinatorial optimization problems. Despite the widespread success of tabu search, researchers have a poor understanding of many key theoretical aspects of this algorithm, including models of the high-level run-time dynamics and identification of those search space features that influence problem difficulty. We consider these questions in the context of the job-shop scheduling problem (JSP), a domain where tabu search algorithms have been shown to be remarkably effective. Previously, we demonstrated that the mean distance between random local optima and the nearest optimal solution is highly correlated with problem difficulty for a well-known tabu search algorithm for the JSP introduced by Taillard. In this paper, we discuss various shortcomings of this measure and develop a new model of problem difficulty that corrects these deficiencies. We show that Taillard’s algorithm can be modeled with high fidelity as a simple variant of a straightforward random walk. The random walk model accounts for nearly all of the variability in the cost required to locate both optimal and sub-optimal solutions to random JSPs, and provides an explanation for differences in the difficulty of random versus structured JSPs. Finally, we discuss and empirically substantiate two novel predictions regarding tabu search algorithm behavior. First, the method for constructing the initial solution is highly unlikely to impact the performance of tabu search. Second, tabu tenure should be selected to be as small as possible while simultaneously avoiding search stagnation; values larger than necessary lead to significant degradations in performance.
タブー探索は、NP困難な多様な組合せ最適化問題に対する高品質解を見つけるための最も効果的なヒューリスティックの一つです。タブー探索は広く成功しているにもかかわらず、研究者はこのアルゴリズムの重要な理論的側面、例えば高水準実行時ダイナミクスのモデル化や、問題の難易度に影響を与える探索空間特性の特定などについて、十分な理解が進んでいません。本稿では、タブー探索アルゴリズムが顕著な有効性を示しているジョブショップスケジューリング問題（JSP）を例に、これらの疑問について考察します。以前、Taylardによって導入されたJSP用のよく知られたタブー探索アルゴリズムにおいて、ランダム局所最適解と最近傍最適解との平均距離が問題の難易度と高い相関関係にあることを示しました。本稿では、この尺度の様々な欠点について考察し、これらの欠点を修正する問題の難易度の新しいモデルを開発します。Taylardのアルゴリズムは、単純なランダムウォークの単純な変種として高い忠実度でモデル化できることを示します。ランダムウォークモデルは、ランダムJSPの最適解と準最適解の両方を見つけるために必要なコストの変動性のほぼすべてを説明し、ランダムJSPと構造化JSPの難易度の違いを説明します。最後に、タブー探索アルゴリズムの挙動に関する2つの新しい予測について議論し、経験的に実証します。第一に、初期解の構築方法がタブー探索の性能に影響を与える可能性は非常に低いということです。第二に、タブー保有期間は、探索の停滞を回避しながら可能な限り小さく選択する必要があります。必要以上に大きな値は、性能の大幅な低下につながります。
Perseus: Randomized Point-based Value Iteration for POMDPs
Perseus：POMDPのためのランダム化ポイントベース価値反復法
Partially observable Markov decision processes (POMDPs) form an attractive and principled framework for agent planning under uncertainty. Point-based approximate techniques for POMDPs compute a policy based on a finite set of points collected in advance from the agent’s belief space. We present a randomized point-based value iteration algorithm called Perseus. The algorithm performs approximate value backup stages, ensuring that in each backup stage the value of each point in the belief set is improved; the key observation is that a single backup may improve the value of many belief points. Contrary to other point-based methods, Perseus backs up only a (randomly selected) subset of points in the belief set, sufficient for improving the value of each belief point in the set. We show how the same idea can be extended to dealing with continuous action spaces. Experimental results show the potential of Perseus in large scale POMDP problems.
部分観測マルコフ決定過程（POMDP）は、不確実性下におけるエージェントプランニングのための魅力的で原理的なフレームワークを形成します。POMDPのポイントベース近似手法は、エージェントの信念空間から事前に収集された有限のポイントセットに基づいてポリシーを計算します。我々は、Perseusと呼ばれるランダム化ポイントベース値反復アルゴリズムを提示します。このアルゴリズムは近似値バックアップステージを実行し、各バックアップステージで信念セット内の各ポイントの値が改善されることを保証します。重要な観察結果は、1回のバックアップで多くの信念ポイントの値が改善される可能性があることです。他のポイントベースの手法とは異なり、Perseusは、確信セット内の各確信ポイントの価値を向上させるのに十分な、（ランダムに選択された）ポイントのサブセットのみをバックアップします。同じアイデアを連続的な行動空間に適用する方法を示します。実験結果は、大規模なPOMDP問題におけるPerseusの潜在能力を示しています。
Learning Content Selection Rules for Generating Object Descriptions in Dialogue
対話におけるオブジェクト記述生成のためのコンテンツ選択規則の学習
A fundamental requirement of any task-oriented dialogue system is the ability to generate object descriptions that refer to objects in the task domain. The subproblem of content selection for object descriptions in task-oriented dialogue has been the focus of much previous work and a large number of models have been proposed. In this paper, we use the annotated COCONUT corpus of task-oriented design dialogues to develop feature sets based on Dale and Reiter’s (1995) incremental model, Brennan and Clark’s (1996) conceptual pact model, and Jordan’s (2000b) intentional influences model, and use these feature sets in a machine learning experiment to automatically learn a model of content selection for object descriptions. Since Dale and Reiter’s model requires a representation of discourse structure, the corpus annotations are used to derive a representation based on Grosz and Sidner’s (1986) theory of the intentional structure of discourse, as well as two very simple representations of discourse structure based purely on recency. We then apply the rule-induction program RIPPER to train and test the content selection component of an object description generator on a set of 393 object descriptions from the corpus. To our knowledge, this is the first reported experiment of a trainable content selection component for object description generation in dialogue. Three separate content selection models that are based on the three theoretical models, all independently achieve accuracies significantly above the majority class baseline (17%) on unseen test data, with the intentional influences model (42.4%) performing significantly better than either the incremental model (30.4%) or the conceptual pact model (28.9%). But the best performing models combine all the feature sets, achieving accuracies near 60%. Surprisingly, a simple recency-based representation of discourse structure does as well as one based on intentional structure. To our knowledge, this is also the first empirical comparison of a representation of Grosz and Sidner’s model of discourse structure with a simpler model for any generation task.
タスク指向対話システムの基本要件は、タスクドメイン内のオブジェクトを参照するオブジェクト記述を生成する能力です。タスク指向対話におけるオブジェクト記述のコンテンツ選択というサブ問題は、これまで多くの研究の焦点となっており、多数のモデルが提案されてきた。本稿では、タスク指向設計対話の注釈付きCOCONUTコーパスを用いて、DaleとReiter (1995)の増分モデル、BrennanとClark (1996)の概念的契約モデル、Jordan (2000b)の意図的影響モデルに基づく特徴セットを開発し、これらの特徴セットを用いて機械学習実験を行い、オブジェクト記述のコンテンツ選択モデルを自動学習します。DaleとReiterのモデルは談話構造の表現を必要とするため、コーパスの注釈を使用して、GroszとSidner (1986)の談話の意図的構造理論に基づく表現と、新しさのみに基づく談話構造の非常に単純な2つの表現を導出します。次に、ルール誘導プログラムRIPPERを適用し、コーパスからの393のオブジェクト記述セットに対してオブジェクト記述ジェネレータのコンテンツ選択コンポーネントのトレーニングとテストを行います。私たちの知る限り、これは対話におけるオブジェクト記述生成のためのトレーニング可能なコンテンツ選択コンポーネントの最初の報告された実験です。3つの理論モデルに基づく3つの個別のコンテンツ選択モデルはすべて独立して、未知のテスト データで多数派クラスのベースライン(17%)を大幅に上回る精度を達成し、意図的影響モデル(42.4%)は増分モデル(30.4%)や概念協定モデル(28.9%)のどちらよりも大幅に優れたパフォーマンスを発揮しました。しかし、最も優れた性能を発揮するモデルはすべての特徴セットを組み合わせ、60%近くの精度を達成しています。驚くべきことに、談話構造の単純な近似値に基づく表現は、意図的構造に基づく表現と同等の精度を達成しています。我々の知る限り、これはGroszとSidnerの談話構造モデルの表現と、任意の生成タスクに対するより単純なモデルとの最初の実証的比較でもあります。
Solving Set Constraint Satisfaction Problems using ROBDDs
ROBDDを用いた集合制約充足問題の解法
In this paper we present a new approach to modeling finite set domain constraint problems using Reduced Ordered Binary Decision Diagrams (ROBDDs). We show that it is possible to construct an efficient set domain propagator which compactly represents many set domains and set constraints using ROBDDs. We demonstrate that the ROBDD-based approach provides unprecedented flexibility in modeling constraint satisfaction problems, leading to performance improvements. We also show that the ROBDD-based modeling approach can be extended to the modeling of integer and multiset constraint problems in a straightforward manner. Since domain propagation is not always practical, we also show how to incorporate less strict consistency notions into the ROBDD framework, such as set bounds, cardinality bounds and lexicographic bounds consistency. Finally, we present experimental results that demonstrate the ROBDD-based solver performs better than various more conventional constraint solvers on several standard set constraint problems.
本稿では、縮退順序付き二分決定図（ROBDD）を用いて有限集合領域制約問題をモデル化する新しい手法を提示します。ROBDDを用いることで、多くの集合領域と集合制約をコンパクトに表現する効率的な集合領域プロパゲータを構築できることを示す。ROBDDベースの手法は制約充足問題のモデル化においてこれまでにない柔軟性を提供し、性能向上につながることを実証します。また、ROBDDベースのモデル化手法は整数制約問題および多重集合制約問題のモデル化にも容易に拡張できることも示す。領域伝播は必ずしも実用的ではないため、集合境界、基数境界、辞書式境界一貫性といった、それほど厳密ではない一貫性の概念をROBDDフレームワークに組み込む方法も示す。最後に、ROBDDベースのソルバーが、いくつかの標準的な集合制約問題において、従来の様々な制約ソルバーよりも優れた性能を発揮することを示す実験結果を示す。
CIXL2: A Crossover Operator for Evolutionary Algorithms Based on Population Features
CIXL2：集団特徴に基づく進化アルゴリズムのための交差演算子
In this paper we propose a crossover operator for evolutionary algorithms with real values that is based on the statistical theory of population distributions. The operator is based on the theoretical distribution of the values of the genes of the best individuals in the population. The proposed operator takes into account the localization and dispersion features of the best individuals of the population with the objective that these features would be inherited by the offspring. Our aim is the optimization of the balance between exploration and exploitation in the search process. In order to test the efficiency and robustness of this crossover, we have used a set of functions to be optimized with regard to different criteria, such as, multimodality, separability, regularity and epistasis. With this set of functions we can extract conclusions in function of the problem at hand. We analyze the results using ANOVA and multiple comparison statistical tests. As an example of how our crossover can be used to solve artificial intelligence problems, we have applied the proposed model to the problem of obtaining the weight of each network in a ensemble of neural networks. The results obtained are above the performance of standard methods.
本論文では、集団分布の統計理論に基づき、実数値を用いた進化アルゴリズムのための交叉演算子を提案します。この演算子は、集団内の最良個体の遺伝子値の理論分布に基づいています。提案された演算子は、集団内の最良個体の局所性と分散性を考慮し、これらの特徴が子孫に継承されるようにします。我々の目的は、探索プロセスにおける探索と利用のバランスを最適化することです。この交叉の効率性と堅牢性を検証するために、マルチモーダル性、分離可能性、規則性、エピスタシスといった様々な基準に基づいて最適化される関数群を用いた。これらの関数群を用いることで、問題に応じた結論を導き出すことができます。結果は、分散分析（ANOVA）と多重比較統計検定を用いて分析します。我々の交叉を人工知能問題の解決にどのように活用できるかを示す例として、ニューラルネットワークのアンサンブルにおける各ネットワークの重みを求める問題に提案モデルを適用した。得られた結果は、標準的な手法を上回る性能を示した。