Journal of Artificial Intelligence Resarch Vol. 20 (2003)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains
PDDL2.1：時間的プランニングドメインを表現するための PDDL の拡張
In recent years research in the planning community has moved increasingly toward s application of planners to realistic problems involving both time and many typ es of resources. For example, interest in planning demonstrated by the space res earch community has inspired work in observation scheduling, planetary rover ex ploration and spacecraft control domains. Other temporal and resource-intensive domains including logistics planning, plant control and manufacturing have also helped to focus the community on the modelling and reasoning issues that must be confronted to make planning technology meet the challenges of application. The International Planning Competitions have acted as an important motivating fo rce behind the progress that has been made in planning since 1998. The third com petition (held in 2002) set the planning community the challenge of handling tim e and numeric resources. This necessitated the development of a modelling langua ge capable of expressing temporal and numeric properties of planning domains. In this paper we describe the language, PDDL2.1, that was used in the competition. We describe the syntax of the language, its formal semantics and the validation of concurrent plans. We observe that PDDL2.1 has considerable modelling power — exceeding the capabilities of current planning technology — and presents a number of important challenges to the research community.
近年、計画コミュニティにおける研究は、時間と多くの種類のリソースの両方を伴う現実的な問題へのプランナーの適用へとますます移行しています。例えば、宇宙研究コミュニティによる計画への関心は、観測スケジュール、惑星探査機探査、宇宙船制御などの分野における研究に影響を与えています。物流計画、プラント制御、製造といった、時間とリソースを大量に消費する他の分野もまた、計画技術をアプリケーションの課題に対応させるために必要なモデリングと推論の問題にコミュニティの焦点を当てるのに役立っています。国際計画コンペティションは、1998年以来、計画における進歩の重要な原動力として機能してきました。第3回コンペティション（2002年開催）では、計画コミュニティに時間と数値リソースの取り扱いという課題が課されました。これにより、計画領域の時間的および数値的特性を表現できるモデリング言語の開発が必要になりました。本稿では、コンペティションで使用された言語PDDL2.1について説明します。本稿では、この言語の構文、形式意味論、および並行プランの検証について説明します。PDDL2.1は、現在のプランニング技術の能力をはるかに超える強力なモデリング能力を備えており、研究コミュニティに多くの重要な課題を提示しています。
VHPOP: Versatile Heuristic Partial Order Planner
VHPOP：汎用ヒューリスティック半順序プランナー
VHPOP is a partial order causal link (POCL) planner loosely based on UCPOP. It draws from the experience gained in the early to mid 1990’s on flaw selection strategies for POCL planning, and combines this with more recent developments in the field of domain independent planning such as distance based heuristics and reachability analysis. We present an adaptation of the additive heuristic for plan space planning, and modify it to account for possible reuse of existing actions in a plan. We also propose a large set of novel flaw selection strategies, and show how these can help us solve more problems than previously possible by POCL planners. VHPOP also supports planning with durative actions by incorporating standard techniques for temporal constraint reasoning. We demonstrate that the same heuristic techniques used to boost the performance of classical POCL planning can be effective in domains with durative actions as well. The result is a versatile heuristic POCL planner competitive with established CSP-based and heuristic state space planners.
VHPOPは、UCPOPを大まかにベースとした半順序因果リンク（POCL）プランナーです。1990年代前半から中頃にかけて得られたPOCLプランニングの欠陥選択戦略に関する経験を活用し、距離ベースのヒューリスティックや到達可能性分析といったドメイン非依存プランニング分野における最近の成果と組み合わせます。本稿では、プラン空間プランニングへの加法的ヒューリスティックの適応を提示し、プラン内の既存アクションの再利用を可能にするように修正します。また、多数の新しい欠陥選択戦略を提案し、これらが従来のPOCLプランナーでは解決できなかった多くの問題を解決する上でどのように役立つかを示します。VHPOPは、時間的制約推論の標準手法を組み込むことで、持続アクションを含むプランニングもサポートします。我々は、古典的なPOCLプランニングの性能向上に用いられるのと同じヒューリスティック手法が、持続アクションを含む領域でも有効であることを示す。その結果、既存のCSPベースおよびヒューリスティックな状態空間プランナーと競合可能な、汎用性の高いヒューリスティックPOCLプランナーが実現した。
SHOP2: An HTN Planning System
SHOP2：HTN プランニングシステム
The SHOP2 planning system received one of the awards for distinguished performance in the 2002 International Planning Competition. This paper describes the features of SHOP2 which enabled it to excel in the competition, especially those aspects of SHOP2 that deal with temporal and metric planning domains.
SHOP2プランニングシステムは、2002年の国際プランニングコンペティションにおいて、優れたパフォーマンスに対して賞の一つを受賞しました。本稿では、コンペティションで優れた成績を収めたSHOP2の特徴、特に時間的および計量的プランニングドメインを扱うSHOP2の側面について説明します。
TALplanner in IPC-2002: Extensions and Control Rules
IPC-2002 における TALplanner：拡張と制御規則
TALplanner is a forward-chaining planner that relies on domain knowledge in the shape of temporal logic formulas in order to prune irrelevant parts of the search space. TALplanner recently participated in the third International Planning Competition, which had a clear emphasis on increasing the complexity of the problem domains being used as benchmark tests and the expressivity required to represent these domains in a planning system. Like many other planners, TALplanner had support for some but not all aspects of this increase in expressivity, and a number of changes to the planner were required. After a short introduction to TALplanner, this article describes some of the changes that were made before and during the competition. We also describe the process of introducing suitable domain knowledge for several of the competition domains.
TALplannerは、時相論理式の形でドメイン知識を活用し、検索空間の無関係な部分を除去する前向き連鎖型プランナーです。TALplannerは最近、第3回国際プランニングコンペティションに参加しました。このコンペティションでは、ベンチマークテストとして使用される問題ドメインの複雑さと、プランニングシステムでこれらのドメインを表現するために必要な表現力の向上に明確な重点が置かれていました。他の多くのプランナーと同様に、TALplannerはこの表現力の向上の一部の側面をサポートしていましたが、すべてをサポートしていたわけではなく、プランナーにいくつかの変更が必要でした。この記事では、TALplannerを簡単に紹介した後、コンペティション前とコンペティション中に加えられた変更の一部について説明します。また、コンペティションのいくつかのドメインに適切なドメイン知識を導入するプロセスについても説明します。
The Metric-FF Planning System: Translating “Ignoring Delete Lists” to Numeric State Variables
メトリック FF プランニングシステム：「削除リストを無視する」を数値状態変数に変換する
Planning with numeric state variables has been a challenge for many years, and was a part of the 3rd International Planning Competition (IPC-3). Currently one of the most popular and successful algorithmic techniques in STRIPS planning is to guide search by a heuristic function, where the heuristic is based on relaxing the planning task by ignoring the delete lists of the available actions. We present a natural extension of “ignoring delete lists” to numeric state variables, preserving the relevant theoretical properties of the STRIPS relaxation under the condition that the numeric task at hand is “monotonic”. We then identify a subset of the numeric IPC-3 competition language, “linear tasks”, where monotonicity can be achieved by pre-processing. Based on that, we extend the algorithms used in the heuristic planning system FF to linear tasks. The resulting system Metric-FF is, according to the IPC-3 results which we discuss, one of the two currently most efficient numeric planners.
数値状態変数を使用した計画は長年の課題であり、第3回国際計画コンペティション(IPC-3)の一部でした。現在、STRIPSプランニングにおいて最も普及し、成功しているアルゴリズム手法の一つは、ヒューリスティック関数によって探索を誘導する手法です。このヒューリスティックは、利用可能なアクションの削除リストを無視することでプランニングタスクを緩和することに基づいています。本稿では、数値タスクが「単調」であるという条件下で、STRIPS緩和の関連する理論的特性を維持しながら、「削除リストを無視する」手法を数値状態変数に自然に拡張する方法を提示します。次に、数値IPC-3競合言語のサブセットである「線形タスク」を特定します。このサブセットでは、前処理によって単調性を実現できます。これに基づき、ヒューリスティックプランニングシステムFFで使用されるアルゴリズムを線形タスクに拡張します。結果として得られるシステムMetric-FFは、本稿で論じるIPC-3の結果によれば、現在最も効率的な2つの数値プランナーのうちの1つです。
Planning Through Stochastic Local Search and Temporal Action Graphs in LPG
LPG における確率的局所探索と時間アクショングラフによる計画
We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting ‘durative actions’ and numerical quantities. These techniques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called ‘Temporal Action Graphs’ (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.
本稿では、最近の標準言語PDDL2.1で規定され、「持続アクション」と数値量をサポートするドメインにおけるプランニングのためのいくつかの手法を紹介します。これらの手法は、第3回国際計画コンペティション(IPC)に参加したドメイン非依存プランナーLPGに実装されています。LPGは、複数の基準に基づいて高品質の計画を作成する増分型のいつでも実行できるシステムです。システムの中核は、確率的局所探索法と「Temporal Action Graphs」(TAグラフ)と呼ばれるグラフベースの表現に基づいています。この論文では、時間的計画に焦点を当て、TAグラフを紹介し、この表現を使用してLPGでの検索をガイドするいくつかの手法を提案します。第3回IPCの実験結果、およびこの論文で提示されたその他の結果は、私たちの手法が非常に効果的であることを示しています。多くの場合、LPGは、ソリューションを導出する速度、または生成できるソリューションの品質の点で、第3回IPCの他のすべての完全自動プランナーよりも優れています。
Taming Numbers and Durations in the Model Checking Integrated Planning System
モデル検査統合計画システムにおける数値と持続の制御
The Model Checking Integrated Planning System (MIPS) is a temporal least commitment heuristic search planner based on a flexible object-oriented workbench architecture. Its design clearly separates explicit and symbolic directed exploration algorithms from the set of on-line and off-line computed estimates and associated data structures. MIPS has shown distinguished performance in the last two international planning competitions. In the last event the description language was extended from pure propositional planning to include numerical state variables, action durations, and plan quality objective functions. Plans were no longer sequences of actions but time-stamped schedules. As a participant of the fully automated track of the competition, MIPS has proven to be a general system; in each track and every benchmark domain it efficiently computed plans of remarkable quality. This article introduces and analyzes the most important algorithmic novelties that were necessary to tackle the new layers of expressiveness in the benchmark problems and to achieve a high level of performance. The extensions include critical path analysis of sequentially generated plans to generate corresponding optimal parallel plans. The linear time algorithm to compute the parallel plan bypasses known NP hardness results for partial ordering by scheduling plans with respect to the set of actions and the imposed precedence relations. The efficiency of this algorithm also allows us to improve the exploration guidance: for each encountered planning state the corresponding approximate sequential plan is scheduled. One major strength of MIPS is its static analysis phase that grounds and simplifies parameterized predicates, functions and operators, that infers knowledge to minimize the state description length, and that detects domain object symmetries. The latter aspect is analyzed in detail. MIPS has been developed to serve as a complete and optimal state space planner, with admissible estimates, exploration engines and branching cuts. In the competition version, however, certain performance compromises had to be made, including floating point arithmetic, weighted heuristic search exploration according to an inadmissible estimate and parameterized optimization.
モデル検査統合計画システム（MIPS）は、柔軟なオブジェクト指向ワークベンチアーキテクチャに基づく、時間的最小コミットメントヒューリスティック探索プランナーです。その設計は、明示的および記号的な有向探索アルゴリズムを、オンラインおよびオフラインで計算される推定値と関連するデータ構造から明確に分離しています。MIPSは、過去2回の国際計画コンペティションにおいて卓越したパフォーマンスを示しました。直近のコンペティションでは、記述言語が純粋な命題計画から拡張され、数値状態変数、行動期間、および計画品質目的関数が含まれるようになりました。計画はもはや行動のシーケンスではなく、タイムスタンプ付きのスケジュールとなりました。コンペティションの完全自動化トラックに参加したMIPSは、汎用システムであることを証明しました。各トラックおよびすべてのベンチマークドメインにおいて、MIPSは驚くほど高品質な計画を効率的に計算しました。本稿では、ベンチマーク問題における新たな表現力の層に対処し、高いパフォーマンスを達成するために必要だった最も重要なアルゴリズムの新機能を紹介し、分析します。これらの拡張機能には、順次生成された計画のクリティカルパス解析から、対応する最適な並列計画を生成する機能が含まれます。並列プランを計算する線形時間アルゴリズムは、アクションの集合と課された優先順位関係に基づいてプランをスケジュールすることにより、部分順序付けにおける既知のNP困難性の結果を回避します。このアルゴリズムの効率性により、探索ガイダンスの改善も可能になります。つまり、遭遇する各プランニング状態に対して、対応する近似逐次プランがスケジュールされます。MIPSの大きな強みの一つは、パラメータ化された述語、関数、演算子をグラウンディングして単純化し、状態記述長を最小化するための知識を推論し、ドメインオブジェクトの対称性を検出する静的解析フェーズです。後者の側面については詳細に分析します。MIPSは、許容推定値、探索エンジン、分岐カットを備えた、完全かつ最適な状態空間プランナーとして機能するように開発されました。しかしながら、競合バージョンでは、浮動小数点演算、許容されない推定値に基づく重み付きヒューリスティック探索、パラメータ化された最適化など、パフォーマンスに関して一定の妥協が必要でした。
SAPA: A Multi-objective Metric Temporal Planner
SAPA：多目的メトリック時間プランナー
SAPA is a domain-independent heuristic forward chaining planner that can handle durative actions, metric resource constraints, and deadline goals. It is designed to be capable of handling the multi-objective nature of metric temporal planning. Our technical contributions include (i) planning-graph based methods for deriving heuristics that are sensitive to both cost and makespan (ii) techniques for adjusting the heuristic estimates to take action interactions and metric resource limitations into account and (iii) a linear time greedy post-processing technique to improve execution flexibility of the solution plans. An implementation of SAPA using many of the techniques presented in this paper was one of the best domain independent planners for domains with metric and temporal constraints in the third International Planning Competition, held at AIPS-02. We describe the technical details of extracting the heuristics and present an empirical evaluation of the current implementation of SAPA.
SAPAは、持続アクション、メトリックリソース制約、および期限目標を扱うことができる、ドメインに依存しないヒューリスティックな前向き連鎖プランナーです。メトリック時間計画の多目的性質に対応できるように設計されています。私たちの技術的貢献には、(i)コストとメイクスパンの両方に敏感なヒューリスティックを導出するためのプランニンググラフベースの手法、(ii)アクションの相互作用とメトリックリソースの制限を考慮してヒューリスティック推定値を調整する手法、(iii)ソリューションプランの実行柔軟性を向上させる線形時間貪欲後処理手法が含まれます。本論文で紹介した多くの手法を用いたSAPAの実装は、AIPS-02で開催された第3回国際計画コンペティションにおいて、メトリック制約と時間制約を持つドメイン向けの最優秀ドメイン独立プランナーの1つに選ばれました。ヒューリスティックの抽出に関する技術的な詳細を説明し、SAPAの現在の実装の実証的評価を示します。
The Case for Durative Actions: A Commentary on PDDL2.1
持続アクションのケース：PDDL2.1 に関する解説
The addition of durative actions to PDDL2.1 sparked some controversy. Fox and Long argued that actions should be considered as instantaneous, but can start and stop processes. Ultimately, a limited notion of durative actions was incorporated into the language. I argue that this notion is still impoverished, and that the underlying philosophical position of regarding durative actions as being a shorthand for a start action, process, and stop action ignores the realities of modelling and execution for complex systems.
PDDL2.1への持続アクションの追加は、いくつかの論争を巻き起こしました。Fox氏とLong氏は、アクションは瞬間的なものと見なすべきであるものの、プロセスを開始および停止できると主張しました。最終的に、持続アクションの限定的な概念が言語に組み込まれました。この概念は依然として不十分であり、持続アクションを開始アクション、プロセス、停止アクションの略語とみなすという根底にある哲学的立場は、複雑システムのモデリングと実行の現実を無視していると私は主張します。
PDDL2.1 — The Art of the Possible? Commentary on Fox and Long
PDDL2.1 — 可能性の芸術？ FoxとLongに関する解説
PDDL2.1 was designed to push the envelope of what planning algorithms can do, and it has succeeded. It adds two important features: durative actions,which take time (and may have continuous effects); and objective functions for measuring the quality of plans. The concept of durative actions is flawed; and the treatment of their semantics reveals too strong an attachment to the way many contemporary planners work. Future PDDL innovators should focus on producing a clean semantics for additions to the language, and let planner implementers worry about coupling their algorithms to problems expressed in the latest version of the language.
PDDL2.1は、プランニング アルゴリズムの可能性の限界を押し広げることを目的として設計され、成功を収めました。2つの重要な機能が追加されました。1つは、時間がかかり(継続的な効果を持つ場合もある)持続アクション、もう1つは、プランの品質を測定するための目的関数です。持続アクションの概念には欠陥があり、そのセマンティクスの扱いは、多くの現代のプランナーの動作方法にあまりにも強く結びついています。将来のPDDLイノベーターは、言語への追加のための明確なセマンティクスを作成することに注力し、プランナーの実装者は、最新バージョンの言語で表現された問題にアルゴリズムを結合することに専念する必要があります。
PDDL 2.1: Representation vs. Computation
PDDL 2.1：表現 vs. 計算
I comment on the PDDL 2.1 language and its use in the planning competition, focusing on the choices made for accommodating time and concurrency. I also discuss some methodological issues that have to do with the move toward more expressive planning languages and the balance needed in planning research between semantics and computation.
本稿では、PDDL 2.1言語と計画コンペティションにおけるその使用について、時間と並行性への対応に関する選択に焦点を当てて解説します。また、より表現力豊かな計画言語への移行と、計画研究においてセマンティクスと計算の間で必要なバランスに関連するいくつかの方法論的問題についても説明します。
Imperfect Match: PDDL 2.1 and Real Applications
不完全な一致：PDDL 2.1と実際のアプリケーション
PDDL was originally conceived and constructed as a lingua franca for the International Planning Competition. PDDL2.1 embodies a set of extensions intended to support the expression of something closer to “real planning problems.” This objective has only been partially achieved, due in large part to a deliberate focus on not moving too far from classical planning models and solution methods.
PDDLはもともと、国際計画コンペティションの共通言語として構想・構築されました。PDDL2.1は、「実際の計画問題」に近い表現を支援するための一連の拡張機能を包含しています。この目標は、従来の計画モデルや解法から大きく逸脱しないように意図的に焦点を当てたため、部分的にしか達成されていません。
The Power of Modeling—a Response to PDDL2.1
モデリングの力：PDDL2.1への応答
In this commentary I argue that although PDDL is a very useful standard for the planning competition, its design does not properly consider the issue of domain modeling. Hence, I would not advocate its use in specifying planning domains outside of the context of the planning competition. Rather, the field needs to explore different approaches and grapple more directly with the problem of effectively modeling and utilizing all of the diverse pieces of knowledge we typically have about planning domains.
本稿では、PDDLは計画コンペティションにおいて非常に有用な標準規格であるものの、その設計はドメインモデリングの問題を適切に考慮していないと主張します。したがって、計画コンペティションの文脈以外で計画ドメインを規定する際にPDDLを使用することは推奨しません。むしろ、この分野は異なるアプローチを模索し、計画ドメインに関する多様な知識を効果的にモデリングし、活用するという問題に、より直接的に取り組む必要があります。
The 3rd International Planning Competition: Results and Analysis
第3回国際プランニングコンペティション：結果と分析
This paper reports the outcome of the third in the series of biennial international planning competitions, held in association with the International Conference on AI Planning and Scheduling (AIPS) in 2002. In addition to describing the domains, the planners and the objectives of the competition, the paper includes analysis of the results. The results are analysed from several perspectives, in order to address the questions of comparative performance between planners, comparative difficulty of domains, the degree of agreement between planners about the relative difficulty of individual problem instances and the question of how well planners scale relative to one another over increasingly difficult problems. The paper addresses these questions through statistical analysis of the raw results of the competition, in order to determine which results can be considered to be adequately supported by the data. The paper concludes with a discussion of some challenges for the future of the competition series.
この論文は、2002年に国際AIプランニングおよびスケジューリング会議(AIPS)と連携して開催された、2年ごとの国際プランニング コンペティションの第3回の結果を報告するものです。コンペティションのドメイン、プランナー、目的の説明に加えて、結果の分析も含まれています。結果は複数の観点から分析され、プランナー間のパフォーマンス比較、ドメインの難易度比較、個々の問題インスタンスの相対的な難易度に関するプランナー間の合意度、そして難易度が増す問題においてプランナー同士がどの程度スケールするかといった疑問に答えています。本論文では、コンペティションの生の結果を統計的に分析することでこれらの疑問に答え、どの結果がデータによって十分に裏付けられているかを判断します。最後に、コンペティションシリーズの将来に向けた課題について考察します。