IPSS: A Hybrid Approach to Planning and Scheduling Integration

Recently, the areas of planning and scheduling in artificial intelligence (AI) have witnessed a big push toward their integration in order to solve complex problems. These problems require both reasoning on which actions are to be performed as well as their precedence constraints (planning) and the reasoning with respect to temporal constraints (e.g., duration, precedence, and deadline); those actions should satisfy the resources they use (scheduling). This paper describes IPSS (integrated planning and scheduling system), a domain independent solver that integrates an AI planner that synthesizes courses of actions with constraint-based techniques that reason based upon time and resources. IPSS is able to manage not only simple precedence constraints, but also more complex temporal requirements (as the Allen primitives) and multicapacity resource usage/consumption. The solver is evaluated against a set of problems characterized by the use of multiple agents (or multiple resources) that have to perform tasks with some temporal restrictions in the order of the tasks or some constraints in the availability of the resources. Experiments show how the integrated reasoning approach improves plan parallelism and gains better makespans than some state-of-the-art planners where multiple agents are represented as additional fluents in the problem operators. It also shows that IPSS is suitable for solving real domains (i.e., workflow problems) because it is able to impose temporal windows on the goals or set a maximum makespan, features that most of the planners do not yet incorporate     

Discovering relational and numerical expressions from plan traces for learning action models

In this paper, we propose a domain learning process build on a machine learning-based process that, starting from plan traces with (partially known) intermediate states, returns a planning domain with numeric predicates, and expressive logical/arithmetic relations between domain predicates written in the planning domain definition language (PDDL). The novelty of our approach is that it can discover relations with little information about the ontology of the target domain to be learned. This is achieved by applying a selection of preprocessing, regression, and classification techniques to infer information from the input plan traces. These techniques are used to prepare the planning data, discover relational/numeric expressions, or extract the preconditions and effects of the domain’s actions. Our solution was evaluated using several metrics from the literature, taking as experimental data plan traces obtained from several domains from the International Planning Competition. The experiments demonstrate that our proposal—even with high levels of incompleteness—correctly learns a wide variety of domains discovering relational/arithmetic expressions, showing F-Score values above 0.85 and obtaining valid domains in most of the experiments.

     

A case-based approach to heuristic planning

Most of the great success of heuristic search as an approach to AI Planning is due to the right design of domain-independent heuristics. Although many heuristic planners perform reasonably well, the computational cost of computing the heuristic function in every search node is very high, causing the planner to scale poorly when increasing the size of the planning tasks. For tackling this problem, planners can incorporate additional domain-dependent heuristics in order to improve their performance. Learning-based planners try to automatically acquire these domain-dependent heuristics using previous solved problems. In this work, we present a case-based reasoning approach that learns abstracted state transitions that serve as domain control knowledge for improving the planning process. The recommendations from the retrieved cases are used as guidance for pruning or ordering nodes in different heuristic search algorithms applied to planning tasks. We show that the CBR guidance is appropriate for a considerable number of planning benchmarks.     

Planning in the Real World

In this article, we describe how real world planning problems can be solved by employing Artificial Intelligence planning techniques. We introduce the paradigm of hybrid planning, which is particularly suited for applications where plans are not intended to be automatically executed by systems, but are made for humans. Hybrid planning combines hierarchical planning – the stepwise refinement of complex tasks – with explicit reasoning about causal dependencies between actions, thereby reflecting exactly the kinds of reasoning humans perform when developing plans. We show how plans are generated and how failed plans are repaired in a way that guarantees stability. Our illustrating examples are taken from a domain model for disaster relief missions enforced upon extensive floods. Finally, we present a tool to support the challenging task of constructing planning domain models.     

Incorporating decision-theoretic planning in a robot architecture

The goal of robotics research is to design a robot to fulfill a variety of tasks in the real world. Inherent in the real world is a high degree of uncertainty about the robot’s behavior and about the world. We introduce a robot task architecture, DTRC, that generates plans with actions that incorporate costs and uncertain effects, and states that yield rewards.The use of a decision-theoretic planner in a robot task architecture is demonstrated on the mobile robot domain of miniature golf. The miniature golf domain shows the application of decision-theoretic planning in an inherently uncertain domain, and demonstrates that by using decision-theoretic planning as the reasoning method in a robot task architecture, accommodation for uncertain information plays a direct role in the reasoning process.     

Aligning Real Process Executions and Prescriptive Process Models through Automated Planning

Modern organizations execute processes to deliver product and services, whose enactment needs to adhere to laws, regulations and standards. Conformance checking is the problem of pinpointing where deviations are observed. This paper shows how instances of the conformance checking problem can be represented as planning problems in PDDL (Planning Domain Definition Language) for which planners can find a correct solution in a finite amount of time. If conformance checking problems are converted into planning problems, one can seamlessly update to the recent versions of the best performing automated planners, with evident advantages in term of versatility and customization. The paper also reports on results of experiments conducted on two real-life case studies and on eight larger synthetic ones, mainly using the Fast-downward planner framework to solve the planning problems due to its performances. Some experiments were also repeated though other planners to concretely showcase the versatility of our approach. The results show that, when process models and event logs are of considerable size, our approach outperforms existing ones even by several orders of magnitude. Even more remarkably, when process models are extremely large and event log traces very long, the existing approaches are unable to terminate because they run out of memory, while our approach is able to properly complete the alignment task.     

Specifying and computing preferred plans

In this paper, we address the problem of specifying and computing preferred plans using rich, qualitative, user preferences. We propose a logical language for specifying preferences over the evolution of states and actions associated with a plan. We provide a semantics for our first-order preference language in the situation calculus, and prove that progression of our preference formulae preserves this semantics. This leads to the development of PPlan, a bounded best-first search planner that computes preferred plans. Our preference language is amenable to integration with many existing planners, and beyond planning, can be used to support a diversity of dynamical reasoning tasks that employ preferences.     

Concise finite-domain representations for PDDL planning tasks

We introduce an efficient method for translating planning tasks specified in the standard PDDL formalism into a concise grounded representation that uses finite-domain state variables instead of the straight-forward propositional encoding.Translation is performed in four stages. Firstly, we transform the input task into an equivalent normal form expressed in a restricted fragment of PDDL. Secondly, we synthesize invariants of the planning task that identify groups of mutually exclusive propositions which can be represented by a single finite-domain variable. Thirdly, we perform an efficient relaxed reachability analysis using logic programming techniques to obtain a grounded representation of the input. Finally, we combine the results of the third and fourth stage to generate the final grounded finite-domain representation.The presented approach has originally been implemented as part of the Fast Downward planning system for the 4th International Planning Competition (IPC4). Since then, it has been used in a number of other contexts with considerable success, and the use of concise finite-domain representations has become a common feature of state-of-the-art planners.     

Planning in the Real World

In this article, we describe how real world planning problems can be solved by employing Artificial Intelligence planning techniques. We introduce the paradigm of hybrid planning, which is particularly suited for applications where plans are not intended to be automatically executed by systems, but are made for humans. Hybrid planning combines hierarchical planning ?C the stepwise refinement of complex tasks ?C with explicit reasoning about causal dependencies between actions, thereby reflecting exactly the kinds of reasoning humans perform when developing plans. We show how plans are generated and how failed plans are repaired in a way that guarantees stability. Our illustrating examples are taken from a domain model for disaster relief missions enforced upon extensive floods. Finally, we present a tool to support the challenging task of constructing planning domain models. The article ends with an overview of a wide varity of actual planning applications and outlines further such in the area of cognitive technical systems.     

基于PDDL的对地观测卫星任务规划建模研究

传统的数学模型方法是解决复杂卫星任务规划问题的一种途径,但其抽象性给建模人员带来很大难度。PDDL(Planning Domain Definition Language)可以针对卫星任务规划问题建立清晰有效的模型,并能把模型的知识转化成计算机易于接受的形式。用PDDL描述对地观测卫星的任务规划问题,分析了卫星执行任务时涉及的约束、相关活动和所需的资源,建立任务规划模型的域文件(domain file)和问题(problem file)文件,并针对所建模型提出求解模型的算法流程,最后通过一个算例验证模型和算法是有效地。     

独立于设计者的行动推理

高水平的智能机器人要求能够独立地对环境进行感知并进行正确的行动推理.在情境演算行动理论中表示带有感知行动及知识的行动推理需要外部设计者为agent写出背景公理、感知结果及相应的知识变化,这是一种依赖于设计者的行动推理.情境演算行动理论被适当扩充,感知器的表示被添加到行动理论的形式语言中,并把agent新知识的产生建立在感知器的应用结果之上.扩充后的系统能够形式化地表示机器人对环境的感知并把感知结果转换为知识,还能进行独立于设计者的行动推理,同时让感知行动的“黑箱”过程清晰化.     

利用派生谓词和偏好处理OSP 问题的目标效益依赖

在过渡规划问题(over-subscribed planning,简称 OSP)研究中,如果目标之间不是相互独立的,那么目标坚定效益依赖比单个目标效益更能提高规划解的质量.但是,已有的描述模型不符合标准规划描述语言(planning domain descrion language,简称PDDL)的语法规范,不能在一般的OSP规划系统上进行推广,提出了用派生谓词规则和目标偏好描述效益依赖的方法,这二者均为ＰDDL语言的基本要素.实质上,将已有的GAI模型转化为派生谓词规则和目标偏好,其中派生谓词规则显式描述目标子集的存在条件,偏好机制用来表示目标子集的效益,二者缺一不可.该转换算法既可以保持在描述依赖关系时GAI模型的易用性和直观性上,又可以扩展一般的OSP规划系统处理目标效益依赖的能力.从理论上可以证明该算法在转化过程中的语义不变性,子啊基准领域的实验结果表明其可行性和规划解质量的改善能力.提出符合PDDL语言规范的目标效益依赖关系的描述形式,克服了已有模型不通用的缺点.     

基于与状态无关的激活集的包含派生谓词的规划问题求解

派生谓词是PDDL2．2语言的新特性之一。在2004年的规划大赛IPC-4上,许多规划系统都无法求解包含派生谓词的两个标准竞赛问题。在经典规划中,派生谓词是指不受领域动作直接影响的谓词,它们在当前状态下的真值是在封闭世界假设中由某些基本谓词通过领域公理推导出来的。本文提出一种新的方法来求解包含派生谓词的规划问题,即用与状态无关的激活集来取代派生谓词用于放宽式规划中。     

Using Many-Sorted Logic in the Object-Oriented Data Model for Fast Robot Task Planning

Search space explosion is a critical problem in robot task planning. This problem limits current robot task planners to solve only simple block world problems and task planning in a real robot working environment to be impractical. This problem is mainly due to the lack of utilization of domain information in task planning. In this paper, we describe a fast task planner for indoor robot applications that effectively uses domain information to speed up the planning process. In this planner, domain information is explicitly represented in an object-oriented data model (OODM) that uses many-sorted logic (MSL) representation. The OODM is convenient for the management of complex data and many-sorted logic is effective for pruning in the rule search process. An inference engine is designed to take advantage of the salient features of these two techniques for fast task planning. A simulation example and complexity analysis are given to demonstrate the advantage of the proposed task planner.     

A STUDY FOR THE APPLICATION OF AUTOMATED PLANNING TO MOBILE ASSISTIVE ROBOTS

In recent years, Automated Planning (AP) has experienced important advances. In this study we apply such advances to the field of Mobile Assistive Robots (MAR). In particular, we propose the use of AP to implement the deliberative step between observation and action execution in MAR. First, we analyze the requirements that allow a MAR to plan navigation and manipulation actions in near real time. The intention is to build the foundation for a planning module within the Simultaneous User Learning and TAsk executioN (SULTAN) architecture, allowing a MAR to perform Daily Life Activities (DLA) in humanlike environments. Second, we apply AP techniques in fully observable, deterministic and static simulated environments with a single MAR. In addition, we analyze and compare the best available satisficing automated planners. The selected planners participate in several experiments to obtain plans for a Planning Domain Definition Language (PDDL) based on the Tidybot domain. Finally, in order to know how competitive the selected planners are, we compare the experimental results in detail.     

Answer set programming for collaborative housekeeping robotics: representation, reasoning, and execution

Answer set programming (ASP) is a knowledge representation and reasoning paradigm with high-level expressive logic-based formalism, and efficient solvers; it is applied to solve hard problems in various domains, such as systems biology, wire routing, and space shuttle control. In this paper, we present an application of ASP to housekeeping robotics. We show how the following problems are addressed using computational methods/tools of ASP: (1) embedding commonsense knowledge automatically extracted from the commonsense knowledge base ConceptNet, into high-level representation, and (2) embedding (continuous) geometric reasoning and temporal reasoning about durations of actions, into (discrete) high-level reasoning. We introduce a planning and monitoring algorithm for safe execution of plans, so that robots can recover from plan failures due to collision with movable objects whose presence and location are not known in advance or due to heavy objects that cannot be lifted alone. Some of the recoveries require collaboration of robots. We illustrate the applicability of ASP on several housekeeping robotics problems, and report on the computational efficiency in terms of CPU time and memory.