Computational Aspects of Reordering Plans
計画の順序付けの計算的側面
This article studies the problem of modifying the action ordering of a plan in order to optimise the plan according to various criteria. One of these criteria is to make a plan less constrained and the other is to minimize its parallel execution time. Three candidate definitions are proposed for the first of these criteria, constituting a sequence of increasing optimality guarantees. Two of these are based on deordering plans, which means that ordering relations may only be removed, not added, while the third one uses reordering, where arbitrary modifications to the ordering are allowed. It is shown that only the weakest one of the three criteria is tractable to achieve, the other two being NP-hard and even difficult to approximate. Similarly, optimising the parallel execution time of a plan is studied both for deordering and reordering of plans. In the general case, both of these computations are NP-hard. However, it is shown that optimal deorderings can be computed in polynomial time for a class of planning languages based on the notions of producers, consumers and threats, which includes most of the commonly used planning languages. Computing optimal reorderings can potentially lead to even faster parallel executions, but this problem remains NP-hard and difficult to approximate even under quite severe restrictions.
本稿では、様々な基準に従ってプランを最適化するために、プランのアクション順序を変更する問題を考察します。これらの基準の一つは、プランの制約を緩和することであり、もう一つは並列実行時間を最小化することです。最初の基準については、最適性保証が増加する一連の規則を構成する3つの候補定義が提案されています。これらのうち2つは、順序関係は削除のみ可能で追加はできないプランの順序付け解除に基づいており、3つ目は順序付けの任意の変更が可能な並べ替えに基づいています。3つの基準のうち、最も弱いものだけが実現可能であり、他の2つはNP困難であり、近似値を求めることすら困難であることが示されます。同様に、プランの順序付け解除と順序付け並べ替えの両方について、プランの並列実行時間の最適化を考察します。一般的なケースでは、これらの計算はどちらもNP困難です。しかし、生産者、消費者、脅威の概念に基づくプランニング言語のクラス（一般的に使用されるプランニング言語のほとんどを含む）では、最適な順序付け解除を多項式時間で計算できることが示されます。最適な並べ替えを計算することで、並列実行をさらに高速化できる可能性がありますが、この問題は依然としてNP困難であり、非常に厳しい制約下でも近似することは困難です。
A Temporal Description Logic for Reasoning about Actions and Plans
行動と計画の推論のための時間的記述論理
A class of interval-based temporal languages for uniformly representing and reasoning about actions and plans is presented. Actions are represented by describing what is true while the action itself is occurring, and plans are constructed by temporally relating actions and world states. The temporal languages are members of the family of Description Logics, which are characterized by high expressivity combined with good computational properties. The subsumption problem for a class of temporal Description Logics is investigated and sound and complete decision procedures are given. The basic language TL-F is considered first: it is the composition of a temporal logic TL — able to express interval temporal networks — together with the non-temporal logic F — a Feature Description Logic. It is proven that subsumption in this language is an NP-complete problem. Then it is shown how to reason with the more expressive languages TLU-FU and TL-ALCF. The former adds disjunction both at the temporal and non-temporal sides of the language, the latter extends the non-temporal side with set-valued features (i.e., roles) and a propositionally complete language.
アクションとプランを一様に表現および推論するための、区間ベースの時相言語のクラスを提示します。アクションは、アクション自体が起こっている間に何が真であるかを記述することによって表現され、プランはアクションと世界の状態を時間的に関連付けられることで構築されます。時相言語は記述論理のファミリーのメンバーであり、優れた計算特性と組み合わされた高い表現力が特徴です。時相記述論理のクラスの包含問題が調査され、健全で完全な決定手順が与えられます。まず、基本言語TL-Fについて検討します。これは、区間時相ネットワークを表現できる時相論理TLと、特徴記述論理である非時相論理Fを組み合わせたものです。この言語における包含はNP完全問題であることが証明されます。次に、より表現力の高い言語TLU-FUとTL-ALCFを使用して推論する方法を示します。前者は言語の時間側と非時間側の両方に選言を追加し、後者は非時間側を集合値特徴(つまり、役割)と命題完全言語で拡張します。
Complexity of Prioritized Default Logics
優先順位付きデフォルト論理の計算量
In default reasoning, usually not all possible ways of resolving conflicts between default rules are acceptable. Criteria expressing acceptable ways of resolving the conflicts may be hardwired in the inference mechanism, for example specificity in inheritance reasoning can be handled this way, or they may be given abstractly as an ordering on the default rules. In this article we investigate formalizations of the latter approach in Reiter’s default logic. Our goal is to analyze and compare the computational properties of three such formalizations in terms of their computational complexity: the prioritized default logics of Baader and Hollunder, and Brewka, and a prioritized default logic that is based on lexicographic comparison. The analysis locates the propositional variants of these logics on the second and third levels of the polynomial hierarchy, and identifies the boundary between tractable and intractable inference for restricted classes of prioritized default theories.
デフォルト推論では、通常、デフォルトルール間の衝突を解決するためのすべての可能な方法が受け入れられるわけではありません。衝突を解決するための許容可能な方法を表現する基準は、推論メカニズムにハードワイヤードされている場合があり、例えば継承推論における詳細度はこのように扱うことができますが、デフォルトルールの順序付けとして抽象的に与えることもできます。本稿では、ライターのデフォルト論理における後者のアプローチの形式化を考察します。私たちの目標は、3つの形式化、すなわちバーダーとホランダー、ブリューカの優先順位付きデフォルト論理、および辞書式比較に基づく優先順位付きデフォルト論理について、計算複雑性の観点から計算特性を分析・比較することです。本分析では、これらの論理の命題的変種を多項式階層の第2レベルと第3レベルに位置付け、優先順位付きデフォルト理論の限定されたクラスについて、扱いやすい推論と扱いにくい推論の境界を特定します。
The Divide-and-Conquer Subgoal-Ordering Algorithm for Speeding up Logic Inference
論理推論を高速化する分割統治法によるサブゴール順序付けアルゴリズム
It is common to view programs as a combination of logic and control: the logic part defines what the program must do, the control part — how to do it. The Logic Programming paradigm was developed with the intention of separating the logic from the control. Recently, extensive research has been conducted on automatic generation of control for logic programs. Only a few of these works considered the issue of automatic generation of control for improving the efficiency of logic programs. In this paper we present a novel algorithm for automatic finding of lowest-cost subgoal orderings. The algorithm works using the divide-and-conquer strategy. The given set of subgoals is partitioned into smaller sets, based on co-occurrence of free variables. The subsets are ordered recursively and merged, yielding a provably optimal order. We experimentally demonstrate the utility of the algorithm by testing it in several domains, and discuss the possibilities of its cooperation with other existing methods.
プログラムは、一般的にロジックと制御の組み合わせとして捉えられます。ロジック部分はプログラムが何をすべきかを定義し、制御部分はそれをどのように行うかを定義します。論理プログラミングパラダイムは、ロジックと制御を分離する目的で開発されました。近年、論理プログラムの制御の自動生成に関する研究が盛んに行われています。これらの研究のうち、論理プログラムの効率を向上させるための制御の自動生成の問題を考慮したものはごくわずかです。本稿では、最小コストのサブゴール順序付けを自動的に見つける新しいアルゴリズムを紹介します。このアルゴリズムは分割統治戦略を用いて動作します。与えられたサブゴールの集合は、自由変数の共起に基づいて、より小さな集合に分割されます。これらのサブセットは再帰的に順序付けられ、マージされることで、証明可能な最適な順序が生成されます。本稿では、いくつかのドメインでこのアルゴリズムをテストすることにより、その有用性を実験的に実証し、他の既存の方法との連携の可能性について議論します。
The Automatic Inference of State Invariants in TIM
TIMにおける状態不変量の自動推論
As planning is applied to larger and richer domains the effort involved in constructing domain descriptions increases and becomes a significant burden on the human application designer. If general planners are to be applied successfully to large and complex domains it is necessary to provide the domain designer with some assistance in building correctly encoded domains. One way of doing this is to provide domain-independent techniques for extracting, from a domain description, knowledge that is implicit in that description and that can assist domain designers in debugging domain descriptions. This knowledge can also be exploited to improve the performance of planners: several researchers have explored the potential of state invariants in speeding up the performance of domain-independent planners. In this paper we describe a process by which state invariants can be extracted from the automatically inferred type structure of a domain. These techniques are being developed for exploitation by STAN, a Graphplan based planner that employs state analysis techniques to enhance its performance.
プランニングがより大規模で豊富なドメインに適用されるにつれて、ドメイン記述の構築にかかる労力は増大し、人間のアプリケーション設計者にとって大きな負担になります。汎用プランナーを大規模で複雑なドメインに適用するには、ドメイン設計者に正しくエンコードされたドメインの構築を支援する必要があります。その方法の1つは、ドメイン記述からその記述に暗黙的に含まれる知識を抽出し、ドメイン設計者がドメイン記述をデバッグするのに役立つようにするための、ドメインに依存しない手法を提供することです。この知識はプランナーのパフォーマンス向上にも活用できます。何人かの研究者が、ドメインに依存しないプランナーのパフォーマンス向上における状態不変条件の可能性を調査してきました。本稿では、ドメインの自動的に推論された型構造から状態不変条件を抽出するプロセスについて説明します。これらの手法は、状態分析手法を使用してパフォーマンスを向上させるGraphplanベースのプランナーであるSTANで活用するために開発されています。
AntNet: Distributed Stigmergetic Control for Communications Networks
AntNet：通信ネットワークのための分散スティグマージ制御
This paper introduces AntNet, a novel approach to the adaptive learning of routing tables in communications networks. AntNet is a distributed, mobile agents based Monte Carlo system that was inspired by recent work on the ant colony metaphor for solving optimization problems. AntNet’s agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. We compare our algorithm with six state-of-the-art routing algorithms coming from the telecommunications and machine learning fields. The algorithms’ performance is evaluated over a set of realistic testbeds. We run many experiments over real and artificial IP datagram networks with increasing number of nodes and under several paradigmatic spatial and temporal traffic distributions. Results are very encouraging. AntNet showed superior performance under all the experimental conditions with respect to its competitors. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority.
本論文では、通信ネットワークにおけるルーティングテーブルの適応学習への新しいアプローチであるAntNetを紹介します。AntNetは、最適化問題を解くための蟻のコロニーメタファーに関する最近の研究に着想を得た、分散型モバイルエージェントベースのモンテカルロシステムです。AntNetのエージェントはネットワークを同時に探索し、収集した情報を交換します。エージェント間の通信は間接的かつ非同期で、ネットワーク自体によって仲介されます。この通信形態は社会性昆虫に典型的であり、スティグマージと呼ばれます。本研究では、このアルゴリズムを、通信および機械学習分野の6つの最先端のルーティングアルゴリズムと比較します。アルゴリズムの性能は、一連の現実的なテストベッドで評価します。ノード数が増加し、いくつかの典型的な空間的および時間的なトラフィック分布の下で、実際のIPデータグラムネットワークと人工のIPデータグラムネットワーク上で多くの実験を行いました。結果は非常に有望です。AntNetは、すべての実験条件下で競合製品よりも優れた性能を示しました。アルゴリズムの主な特徴を分析し、その優位性の理由を説明します。
The Ariadne’s Clew Algorithm
アリアドネのクルーアルゴリズム
We present a new approach to path planning, called the “Ariadne’s clew algorithm”. It is designed to find paths in high-dimensional continuous spaces and applies to robots with many degrees of freedom in static, as well as dynamic environments — ones where obstacles may move. The Ariadne’s clew algorithm comprises two sub-algorithms, called SEARCH and EXPLORE, applied in an interleaved manner. EXPLORE builds a representation of the accessible space while SEARCH looks for the target. Both are posed as optimization problems. We describe a real implementation of the algorithm to plan paths for a six degrees of freedom arm in a dynamic environment where another six degrees of freedom arm is used as a moving obstacle. Experimental results show that a path is found in about one second without any pre-processing.
本稿では、「アリアドネの手がかりアルゴリズム」と呼ばれる経路計画への新しいアプローチを紹介します。これは、高次元連続空間における経路探索を目的として設計されており、静的環境だけでなく、障害物が移動する可能性のある動的環境においても、多自由度ロボットに適用されます。アリアドネの手がかりアルゴリズムは、SEARCHとEXPLOREと呼ばれる2つのサブアルゴリズムで構成され、交互に適用されます。EXPLOREはアクセス可能な空間の表現を構築し、SEARCHはターゲットを探します。どちらも最適化問題として提示されます。本稿では、6自由度アームが移動する障害物として使用される動的環境において、別の6自由度アームの経路を計画するためのアルゴリズムの実際の実装について説明します。実験結果によると、前処理なしで約1秒で経路が見つかることが示されています。
An Empirical Approach to Temporal Reference Resolution
時間的参照解決への経験的アプローチ
Scheduling dialogs, during which people negotiate the times of appointments, are common in everyday life. This paper reports the results of an in-depth empirical investigation of resolving explicit temporal references in scheduling dialogs. There are four phases of this work: data annotation and evaluation, model development, system implementation and evaluation, and model evaluation and analysis. The system and model were developed primarily on one set of data, and then applied later to a much more complex data set, to assess the generalizability of the model for the task being performed. Many different types of empirical methods are applied to pinpoint the strengths and weaknesses of the approach. Detailed annotation instructions were developed and an intercoder reliability study was performed, showing that naive annotators can reliably perform the targeted annotations. A fully automatic system has been developed and evaluated on unseen test data, with good results on both data sets. We adopt a pure realization of a recency-based focus model to identify precisely when it is and is not adequate for the task being addressed. In addition to system results, an in-depth evaluation of the model itself is presented, based on detailed manual annotations. The results are that few errors occur specifically due to the model of focus being used, and the set of anaphoric relations defined in the model are low in ambiguity for both data sets.
人々が予定の時間を交渉するスケジュール設定ダイアログは、日常生活においてよく見られるものです。本論文では、スケジュール設定ダイアログにおける明示的な時間的参照の解決に関する詳細な実証的調査の結果を報告するものです。この研究は、データのアノテーションと評価、モデルの開発、システムの実装と評価、そしてモデルの評価と分析という4つの段階から構成されています。システムとモデルは、まず1つのデータセットを用いて開発され、その後、より複雑なデータセットに適用され、実行中のタスクに対するモデルの一般化可能性を評価しました。このアプローチの長所と短所を特定するために、様々な実証的手法が用いられました。詳細なアノテーション指示が開発され、インターコーダー信頼性調査が実施されました。その結果、初心者のアノテーターでも、対象とするアノテーションを確実に実行できることが示されました。完全自動システムを開発し、未公開のテストデータを用いて評価したところ、両方のデータセットで良好な結果が得られました。本研究では、近近性に基づくフォーカスモデルの純粋な実現を採用し、それが対象とするタスクに適している場合と適していない場合を正確に特定します。システムの結果に加えて、詳細な手動注釈に基づくモデル自体の詳細な評価も提示します。その結果、使用されている焦点モデルに起因するエラーはほとんど発生せず、モデルで定義されたアナフォリック関係の集合は、両方のデータセットにおいて曖昧性が低いことがわかりました。
The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem
ハミルトン閉路問題におけるGn,m相転移は困難ではない
Using an improved backtrack algorithm with sophisticated pruning techniques, we revise previous observations correlating a high frequency of hard to solve Hamiltonian Cycle instances with the Gn,m phase transition between Hamiltonicity and non-Hamiltonicity. Instead all tested graphs of 100 to 1500 vertices are easily solved. When we artificially restrict the degree sequence with a bounded maximum degree, although there is some increase in difficulty, the frequency of hard graphs is still low. When we consider more regular graphs based on a generalization of knight’s tours, we observe frequent instances of really hard graphs, but on these the average degree is bounded by a constant. We design a set of graphs with a feature our algorithm is unable to detect and so are very hard for our algorithm, but in these we can vary the average degree from O(1) to O(n). We have so far found no class of graphs correlated with the Gn,m phase transition which asymptotically produces a high frequency of hard instances.
洗練された枝刈り技術を用いた改良型バックトラックアルゴリズムを用いることで、ハミルトン閉路の解くのが難しい事例が高頻度に発生するというこれまでの観察結果を修正します。その結果、100～1500頂点のテスト済みグラフはすべて容易に解けるようになった。次数列を最大次数で人為的に制限すると、解くのが困難になるものの、解くのが難しいグラフの頻度は依然として低い。ナイトツアーの一般化に基づくより規則的なグラフを考えると、非常に解くのが難しいグラフの事例が頻繁に発生するが、これらのグラフでは平均次数は定数で制限されます。我々は、アルゴリズムが検出できない特徴を持つグラフの集合を設計します。これらのグラフは、アルゴリズムにとって非常に困難であるが、平均次数をO(1)からO(n)まで変化させることができます。これまでのところ、漸近的に解くのが困難な事例が高頻度に発生するGn,m相転移と相関するグラフのクラスは見つかっていない。
Probabilistic Inference from Arbitrary Uncertainty using Mixtures of Factorized Generalized Gaussians
因子分解された一般化ガウス分布の混合を用いた任意の不確実性からの確率的推論
This paper presents a general and efficient framework for probabilistic inference and learning from arbitrary uncertain information. It exploits the calculation properties of finite mixture models, conjugate families and factorization. Both the joint probability density of the variables and the likelihood function of the (objective or subjective) observation are approximated by a special mixture model, in such a way that any desired conditional distribution can be directly obtained without numerical integration. We have developed an extended version of the expectation maximization (EM) algorithm to estimate the parameters of mixture models from uncertain training examples (indirect observations). As a consequence, any piece of exact or uncertain information about both input and output values is consistently handled in the inference and learning stages. This ability, extremely useful in certain situations, is not found in most alternative methods. The proposed framework is formally justified from standard probabilistic principles and illustrative examples are provided in the fields of nonparametric pattern classification, nonlinear regression and pattern completion. Finally, experiments on a real application and comparative results over standard databases provide empirical evidence of the utility of the method in a wide range of applications.
本論文では、任意の不確実情報から確率推論と学習を行うための、汎用的かつ効率的な枠組みを提示します。この枠組みは、有限混合モデル、共役族、および因数分解の計算特性を利用します。変数の同時確率密度と（客観的または主観的）観測値の尤度関数の両方を、特殊な混合モデルによって近似することで、数値積分を必要とせずに任意の条件付き分布を直接得ることができます。我々は、不確実な学習例（間接観測値）から混合モデルのパラメータを推定するための、期待値最大化（EM）アルゴリズムの拡張版を開発した。その結果、入力値と出力値の両方に関する正確な情報または不確実な情報は、推論段階と学習段階において一貫して扱われます。この機能は特定の状況では非常に有用であるが、他の多くの手法には見られない。提案された枠組みは、標準的な確率論的原理に基づいて形式的に正当化されており、ノンパラメトリックパターン分類、非線形回帰、パターン補完の分野における実例が示されています。最後に、実際のアプリケーションにおける実験と標準データベースとの比較結果により、この手法が幅広いアプリケーションにおいて有用であることを実証的に証明します。
Adaptive Parallel Iterative Deepening Search
適応型並列反復深化探索
Many of the artificial intelligence techniques developed to date rely on heuristic search through large spaces. Unfortunately, the size of these spaces and the corresponding computational effort reduce the applicability of otherwise novel and effective algorithms. A number of parallel and distributed approaches to search have considerably improved the performance of the search process. Our goal is to develop an architecture that automatically selects parallel search strategies for optimal performance on a variety of search problems. In this paper we describe one such architecture realized in the Eureka system, which combines the benefits of many different approaches to parallel heuristic search. Through empirical and theoretical analyses we observe that features of the problem space directly affect the choice of optimal parallel search strategy. We then employ machine learning techniques to select the optimal parallel search strategy for a given problem space. When a new search task is input to the system, Eureka uses features describing the search space and the chosen architecture to automatically select the appropriate search strategy. Eureka has been tested on a MIMD parallel processor, a distributed network of workstations, and a single workstation using multithreading. Results generated from fifteen puzzle problems, robot arm motion problems, artificial search spaces, and planning problems indicate that Eureka outperforms any of the tested strategies used exclusively for all problem instances and is able to greatly reduce the search time for these applications.
これまでに開発された多くの人工知能技術は、広大な空間を介したヒューリスティックな探索に依存しています。しかしながら、これらの空間の規模とそれに伴う計算負荷は、本来であれば斬新で効果的なアルゴリズムの適用性を低下させています。探索に対する多くの並列・分散アプローチは、探索プロセスの性能を大幅に向上させてきた。我々の目標は、様々な探索問題において最適な性能を発揮する並列探索戦略を自動的に選択するアーキテクチャを開発することです。本稿では、Eurekaシステムで実現された、並列ヒューリスティック探索に対する様々なアプローチの利点を組み合わせたアーキテクチャの1つについて説明します。経験的および理論的分析を通して、問題空間の特徴が最適な並列探索戦略の選択に直接影響を与えることを観察します。次に、機械学習技術を用いて、与えられた問題空間に最適な並列探索戦略を選択します。新しい探索タスクがシステムに入力されると、Eurekaは探索空間と選択されたアーキテクチャを記述する特徴を用いて、適切な探索戦略を自動的に選択します。Eurekaは、MIMD並列プロセッサ、ワークステーションの分散ネットワーク、そしてマルチスレッド処理を用いた単一のワークステーションでテストされています。15個のパズル問題、ロボットアームのモーション問題、人工探索空間、そしてプランニング問題から得られた結果は、Eurekaが全ての問題インスタンスに対して単独で使用されたテスト済みのどの戦略よりも優れた性能を示し、これらのアプリケーションにおける探索時間を大幅に短縮できることを示しました。
The Computational Complexity of Probabilistic Planning
確率的プランニングの計算複雑性
We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.
我々は、フラット表現と命題表現の両方を用いた確率的計画ドメインにおける小規模プランのテストと発見の計算複雑性を検証します。プランの評価と存在の複雑性は、求められるプランの種類によって異なります。我々は、全順序プラン、非巡回プラン、ループプラン、そしてプラン値の3つの自然な定義に基づく部分順序プランを検証します。我々は、関心対象の問題が、PL、P、NP、co-NP、PP、NP^PP、co-NP^PP、PSPACEといった様々な複雑性クラスに対して完全であることを示す。特定の計画問題がNP^PPに対して完全であることを証明する過程で、我々は新たな基本的なNP^PP完全問題であるE-MAJSATを導入します。これは、標準的なブール充足可能性問題を確率量を含む計算に一般化するものです。我々の結果は、E-MAJSATに適したヒューリスティックスの開発が、様々な問題に対する効率的なアルゴリズムの開発に重要となる可能性を示唆しています。