Group planning with time constraints

Embedding planning systems in real-world domains has led to the necessity of Distributed Continual Planning (DCP) systems where planning activities are distributed across multiple agents and plan generation may occur concurrently with plan execution. A key challenge in DCP systems is how to coordinate activities for a group of planning agents. This problem is compounded when these agents are situated in a real-world dynamic domain where the agents often encounter differing, incomplete, and possibly inconsistent views of their environment. To date, DCP systems have only focused on cases where agents’ behavior is designed to optimize a global plan. In contrast, this paper presents a temporal reasoning mechanism for self-interested planning agents. To do so, we model agents’ behavior based on the Belief-Desire-Intention (BDI) theoretical model of cooperation, while modeling dynamic joint plans with group time constraints through creating hierarchical abstraction plans integrated with temporal constraints network. The contribution of this paper is threefold: (i) the BDI model specifies a behavior for self interested agents working in a group, permitting an individual agent to schedule its activities in an autonomous fashion, while taking into consideration temporal constraints of its group members; (ii) abstract plans allow the group to plan a joint action without explicitly describing all possible states in advance, making it possible to reduce the number of states which need to be considered in a BDI-based approach; and (iii) a temporal constraints network enables each agent to reason by itself about the best time for scheduling activities, making it possible to reduce coordination messages among a group. The mechanism ensures temporal consistency of a cooperative plan, enables the interleaving of planning and execution at both individual and group levels. We report on how the mechanism was implemented within a commercial training and simulation application, and present empirical evidence of its effectiveness in real-life scenarios and in reducing communication to coordinate group members’ activities.     

A model of reaction for planning in dynamic environments

One shortcoming with most AI planning systems has been an inability to deal with execution-time discrepancies between actual and expected situations. Often, these exception situations jeopardize the immediate integrity and safety of the planning agent or its surroundings, with the only recourse being more time-consuming plan generation. In order to avoid such situations, potential exceptions must be predicted during plan execution. Since many application domains (particularly for autonomous systems) are inherently dynamic — in the sense that information is at best incomplete, perhaps erroneous, and changes over time independent of a planning agent's actions — managing action in the world becomes a difficult problem. Action and events in dynamic worlds must be monitored in order to coordinate an agent's actions with its surroundings. This allows the agent to predict and plan for potential future exception situations while acting in the present.This paper introduces an approach to autonomous reaction in dynamic environments. We have avoided the traditional distinction between generating and then executing plans through the use of a dynamic reaction system, which handles potential exception situations gracefully as it carries out assigned tasks. The reaction system manages constraints imposed by ongoing activity in the world, as well as those derived from long-term planning, to control observable behaviour. This approach provides the necessary stimulus/response behaviour required in dynamic situations, while using goal-directed constraints as heuristics for improved reactions.We present an overview of the salient features of dynamic worlds and their impact on traditional planning, introduce our model of dynamic reactivity, describe an implementation of the model and its performance in a dynamic simulation environment, and present an architecture incorporating long-term planning with short-term reactance suitable for autonomous systems applications.     

Hierarchical planning involving deadlines, travel time, and resources

This paper describes a planning architecture that supports a form of hierarchical planning well suited to applications involving deadlines, travel time, and resource considerations. The architecture is based upon a temporal database, a heuristic evaluator, and a decision procedure for refining partial plans. A partial plan consists of a set of tasks and constraints on their order, duration, and potential resource requirements. The temporal database records the partial plan that the planner is currently working on and computes certain consequences of that information to be used in proposing methods to further refine the plan. The heuristic evaluator examines the space of linearized extensions of a given partial plan in order to reject plans that fail to satisfy basic requirements (e.g., hard deadlines and resource limitations) and to estimate the utility of plans that meet these requirements. The information provided by the temporal database and the heuristic evaluator is combined using a decision procedure that determines how best to refine the current partial plan. Neither the temporal database nor the heuristic evaluator is complete and, without reasonably accurate information concerning the possible resource requirements of the tasks in a partial plan, there is a significant risk of missing solutions. A specification language that serves to encode expectations concerning the duration and resource requirements of tasks greatly reduces this risk, enabling useful evaluations of partial plans. Details of the specification language and examples illustrating how such expectations are exploited in decision making are provided.     

Cooperation Requirements Planning (CRP) for multiprocessors: Optimal assignment and execution planning

Cooperation is considered an essential attribute of intelligent multi-machine systems. It enhances their flexibility and reliability. Cooperation Requirement Planning (CRP) is the process of generating a consistent and coordinated global execution plan for a set of tasks to be completed by a multi-machine system based on the task cooperation requirements and interactions. CRP is divided into two steps: CRP-I which matches the task requirements to machine and system capabilities to generate cooperation requirements. It also generates task precedence, machine operation, and system resource constraints. CRP-II uses the cooperation requirements and various constraints to generate a task assignment and coordinated and consistent global execution plan. The global execution plan specifies an ordered sequence of actions and the machine sets that execute them such that the assigned tasks are successfully completed, all the constraints are resolved, and the desired performance measure optimized.In this paper, we describe the CRP-II methodology based on the concepts of planning for multiple goals with interactions. Each task is considered to be a goal, and the CRP-I process is viewed as generating alternate plans and associated costs to accomplish each goal. Five different interactions are specified between the various plans: action combination, precedence relation, resource sharing, cooperative action, and independent action. The CRP-II process is viewed as selecting a plan to satisfy each goal and resolving the interactions between them. A planning strategy is proposed which performs plan selection and interaction resolution simultaneously using a best-first search process to generate the optimal global plan.     

基于鞍点法的自适应分布式资源分配算法

研究一类带有不等式约束为凸函数的多智能体系统分布式资源分配问题.在资源分配问题中,各智能体拥有仅自身可知的局部成本函数和局部凸不等式约束.分布式资源分配旨在如何利用智能体间的信息交互设计一种分布式优化算法,完成定量资源分配的同时还保证最小化全局成本函数.针对该问题,基于卡罗需-库恩-塔克条件和比例积分控制思想,首先提出一种自适应分布式优化算法,其中凸不等式约束的对偶变量可实现自适应获取;然后,为了降低系统的通信资源消耗,设计一种动态事件触发控制策略以实现离散时间通信的分布式资源分配算法;最后,通过数值仿真验证所设计算法的有效性.     

General Temporal Knowledge for Planning and Data Mining

We consider the architecture of systems that combine temporal planning and plan execution and introduce a layer of temporal reasoning that potentially improves both the communication between humans and such systems, and the performance of the temporal planner itself. In particular, this additional layer simultaneously supports more flexibility in specifying and maintaining temporal constraints on plans within an uncertain and changing execution environment, and the ability to understand and trace the progress of plan execution. It is shown how a representation based on single set of abstractions of temporal information can be used to characterize the reasoning underlying plan generation and execution interpretation. The complexity of such reasoning is discussed.     

Constraint satisfaction for planning and scheduling problems

The areas of planning and scheduling (from the Artificial Intelligence point of view) have seen important advances thanks to application of constraint satisfaction techniques. Currently, many important real-world problems require efficient constraint handling for planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Solutions to these problems require integration of resource allocation and plan synthesis capabilities. Hence to manage such complex problems planning, scheduling and constraint satisfaction must be interrelated. This special issue on Constraint Satisfaction for Planning and Scheduling Problems compiles a selection of papers dealing with various aspects of applying constraint satisfaction techniques in planning and scheduling. The core of submitted papers was formed by the extended versions of papers presented at COPLAS??2009: ICAPS 2009 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research.     

A Task Allocation Method for Stream Processing with Recovery Latency Constraint

Stream processing applications continuously process large amounts of online streaming data in real time or near real time. They have strict latency constraints. However, the continuous processing makes them vulnerable to any failures, and the recoveries may slow down the entire processing pipeline and break latency constraints. The upstream backup scheme is one of the most widely applied fault-tolerant schemes for stream processing systems. It introduces complex backup dependencies to tasks, which increases the difficulty of controlling recovery latencies. Moreover, when dependent tasks are located on the same processor, they fail at the same time in processor-level failures, bringing extra recovery latencies that increase the impacts of failures. This paper studies the relationship between the task allocation and the recovery latency of a stream processing application. We present a correlated failure effect model to describe the recovery latency of a stream topology in processor-level failures under a task allocation plan. We introduce a recovery-latency aware task allocation problem (RTAP) that seeks task allocation plans for stream topologies that will achieve guaranteed recovery latencies. We discuss the difference between RTAP and classic task allocation problems and present a heuristic algorithm with a computational complexity of O(n log² n) to solve the problem. Extensive experiments were conducted to verify the correctness and effectiveness of our approach. It improves the resource usage by 15%–20% on average.     

面向Flink迭代作业的动态资源分配策略

新兴分布式计算框架Apache Flink支持在集群上执行大规模的迭代程序,但其默认的静态资源分配机制导致无法进行合理的资源配置来使迭代作业按时完成.针对这一问题,应该依靠用户来主动表达性能约束而不是被动地进行资源保留,故提出了一种基于运行时间预测的动态资源分配策略RABORP (resource allocation...     

A simulation test-bed for mobile adaptive architectures

Existing mobile systems are typically highly constrained with regards to their run-time resources: CPU, memory, communication bandwidth, screen real-estate, battery, and so forth. In current mobile systems, resource allocation decisions are almost always fixed at the time of system creation. However, this situation is arguably changing as mobile systems are becoming more powerful and as the demands being placed upon them are also increasing dramatically. For this reason, such systems need effective methods to manage and control their resources at run-time, particularly in the face of changing environmental conditions and user needs. This paper presents a simulation test-bed for experimenting with architectural design decisions such as communication and negotiation strategies among components, scheduling algorithms, and usability considerations. One significant area that we have begun to experiment with is the use of user-defined “utility” as a means of making dynamic resource allocation decisions. We will discuss the use of utility as a guide for scheduling, describe the test-bed, and present some examples of the results that we have derived, comparing utility-based scheduling with traditional scheduling methods.     

An Introduction to Interactive Discourse Processing from the Perspective of Plan Recognition and Text Planning

People engage in task-oriented dialogues to carry out or plan a task. Each participant in such an interaction must be capable of processing plans in two ways. First, each participant must be capable of understanding the plans that the other participant is using. Researchers have developed theories and models about how computational systems should go about recognizing the plans and goals of another participant, both at the subject-matter level and at the level of the communication. This area of research is called plan recognition. Secondly, each participant must be able to make their owns plans to communicate. This area of natural language research is called text planning.Interactive systems -- systems that understand natural language and that can produce natural language to engage in a task-related interaction -- must address the issue of how understanding plans (the process of plan recognition) relates to making plans for the interaction (the process of text planning). We provide an introduction to these two research areas in natural language processing. Those who need to be familiar with both areas -- to conduct research at their intersection -- will find this introduction useful for building systems that both understand what people are trying to do when they speak and that can actively participate in the interaction.     

Planning and Resource Allocation for Hard Real-time,Fault-Tolerant Plan Execution

We describe the interface between a real-time resource allocation system with an AI planner in order to create fault-tolerant plans that are guaranteed to execute in hard real-time. The planner specifies the task set and all execution deadlines required to ensure system safety, then the resource utilization. A new interface module combines information from planning and resource allocation to enforce development of plans feasible for execution during a variety of internal system faults. Plans that over-utilize any system resource trigger feedback to the planner, which then searches for an alternate plan. A valid plan for each specified fault, including the nominal no-fault situation, is stored in a plan cache for subsequent real-time execution. We situate this work in the context of CIRCA, the Cooperative Intelligent Real-time Control Architecture, which focuses on developing and scheduling plans that make hard real-time safety guarantees, and provide an example of an autonomous aircraft agent to illustrate how our planner-resource allocation interface improves CIRCA performance.     

Multi-task emotion communication system with dynamic resource allocations

The research of long-distance emotion communication and interaction without time and space constraints is an important area in human-robot interaction (HRI) systems. Although many methods of emotion recognition have been studied for analyzing various emotion signals, the resource allocation of transmission for emotion communication signals of many pairs of users has not been fully considered nor solved at the same time. This paper proposes a new multi-task emotion communication system (MEmSys), where the transmission resources allocation issue is considered. Specifically, we firstly establish the architecture of MEmSys, and the entire emotion interaction process of the proposed system is introduced. By analyzing fairness and urgency of different tasks, the mathematical expressions of the minimum task transmission rates for all user pairs are derived. Then, a dynamic optimal resource allocation scheme is presented to maximize the sum of the task transmission rates in the proposed system. Moreover, simulation experiment results and performance analyses show that the resource utilization ratio of the proposed allocation scheme for multiple user pairs is significantly improved compared to the single user pair system. Finally, future works are discussed to provide insights for our next research.     

Application of genetic algorithm to computer-aided process planning in distributed manufacturing environments

In a distributed manufacturing environment, factories possessing various machines and tools at different geographical locations are often combined to achieve the highest production efficiency. When jobs requiring several operations are received, feasible process plans are produced by those factories available. These process plans may vary due to different resource constraints. Therefore, obtaining an optimal or near-optimal process plan becomes important. This paper presents a genetic algorithm (GA), which, according to prescribed criteria such as minimizing processing time, could swiftly search for the optimal process plan for a single manufacturing system as well as distributed manufacturing systems. By applying the GA, the computer-aided process planning (CAPP) system can generate optimal or near-optimal process plans based on the criterion chosen. Case studies are included to demonstrate the feasibility and robustness of the approach. The main contribution of this work lies with the application of GA to CAPP in both a single and distributed manufacturing system. It is shown from the case study that the approach is comparative or better than the conventional single-factory CAPP.     

Anytime search in dynamic graphs

Agents operating in the real world often have limited time available for planning their next actions. Producing optimal plans is infeasible in these scenarios. Instead, agents must be satisfied with the best plans they can generate within the time available. One class of planners well-suited to this task are anytime planners, which quickly find an initial, highly suboptimal plan, and then improve this plan until time runs out.A second challenge associated with planning in the real world is that models are usually imperfect and environments are often dynamic. Thus, agents need to update their models and consequently plans over time. Incremental planners, which make use of the results of previous planning efforts to generate a new plan, can substantially speed up each planning episode in such cases.In this paper, we present an A^∗-based anytime search algorithm that produces significantly better solutions than current approaches, while also providing suboptimality bounds on the quality of the solution at any point in time. We also present an extension of this algorithm that is both anytime and incremental. This extension improves its current solution while deliberation time allows and is able to incrementally repair its solution when changes to the world model occur. We provide a number of theoretical and experimental results and demonstrate the effectiveness of the approaches in a robot navigation domain involving two physical systems. We believe that the simplicity, theoretical properties, and generality of the presented methods make them well suited to a range of search problems involving dynamic graphs.     

CTP: A New Constraint-Based Formalism for Conditional, Temporal Planning

Temporal constraints pose a challenge for conditional planning, because it is necessary for a conditional planner to determine whether a candidate plan will satisfy the specified temporal constraints. This can be difficult, because temporal assignments that satisfy the constraints associated with one conditional branch may fail to satisfy the constraints along a different branch. In this paper we address this challenge by developing the Conditional Temporal Problem (CTP) formalism, an extension of standard temporal constraint-satisfaction processing models used in non-conditional temporal planning. Specifically, we augment temporal CSP frameworks by (1) adding observation nodes, and (2) attaching labels to all nodes to indicate the situation(s) in which each will be executed. Our extended framework allows for the construction of conditional plans that are guaranteed to satisfy complex temporal constraints. Importantly, this can be achieved even while allowing for decisions about the precise timing of actions to be postponed until execution time, thereby adding flexibility and making it possible to dynamically adapt the plan in response to the observations made during execution. We also show that, even for plans without explicit quantitative temporal constraints, our approach fixes a problem in the earlier approaches to conditional planning, which resulted in their being incomplete.     

An operational optimization procedure for production scheduling

The methodology takes a sufficiently long time horizon and breaks the problem into two subproblems. The first subproblem is the long range planning model and the second the short run production scheduling model. The long range model is essentially a resource constrained model and has a linear programming formulation with a profit maximization objective function. The long range plan fixes the discretionary marketing variables, such as the selection of product line, and the timing and extent of promotional sales. It estimates manpower requirements and establishes the raw material procurement plans. Lagrange multipliers obtained in the long range model are then used in the short run production scheduling model. The scheduling algorithm, having a Lagrangian function for an objective, is the solution to an unconstrained maximization problem. This then reduces to one of sequential allocation of production facilities to products. The algorithm is being applied on a problem with five production lines, 126 products, 26 time periods and 32 raw material constraints.     

数字孪生甬江流域水资源“四预”应用研究

基于当前数字孪生流域发展背景及宁波市水资源利用特点，为满足宁波市水资源在不同时空下合理分配的需求，以甬江流域水资源管理与调配“四预”流程为切入点，深度融合数字孪生、BIM 建模等现代化信息技术，在建立来水预报分析、需水预测、水资源优化调配、水资源实时分析评价及水资源预警等各类模型的基础上， 构建具有“预报分析—监测预警—调配预演—调度预案—动态评价”功能的水资源管理与调配业务应用系统，以达到及时准确预报、全面精准预警、同步仿真预演、精细数字预案、多维动态评价的目标，最终实现水资源的智能优化调配与管理。     

Diagnosing resource usage failures in multi-agent systems

In the not-so-far future, autonomous vehicles will be ubiquitous and, consequently, need to be coordinated to avoid traffic jams and car accidents. A failure in one or more autonomous vehicles may break this coordination, resulting in reduced efficiency (due to traffic load) or even bodily harm (due to accidents). The challenge we address in this paper is to identify the root cause of such failures. Identifying the faulty vehicles in such cases is crucial in order to know which vehicles to repair to avoid future failures as well as for determining accountability (e.g., for legal purposes). More generally, this paper discusses multi-agent systems (MAS) in which the agents use a shared pool of resources and they coordinate to avoid resource contention by agreeing on a temporal resource allocation. The problem we address, called the Temporal Multi-Agent Resource Allocation (TMARA) diagnosis problem (TMARA-Diag), is to find the root cause of failures in such MAS that are caused by malfunctioning agents that use resources not allocated to them. As in the autonomous vehicles example, such failures may cause the MAS to perform suboptimally or even fail, potentially causing a chain reaction of failures, and we aim to identify the root cause of such failures, i.e., which agents did not follow the planned resource allocation. We show how to formalize TMARA-Diag as a model-based diagnosis problem and how to compile it to a set of logical constraints that can be compiled to Boolean satisfiability (SAT) and solved efficiently with modern SAT solvers. Importantly, the proposed solution does not require the agents to share their actual plans, only the agreed upon temporal resource allocation and the resources used at the time of failure. Such solutions are key in the development and success of intelligent, large, and security-aware MAS.     

Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners

The international planning competition (IPC) is an important driver for planning research. The general goals of the IPC include pushing the state of the art in planning technology by posing new scientific challenges, encouraging direct comparison of planning systems and techniques, developing and improving a common planning domain definition language, and designing new planning domains and problems for the research community. This paper focuses on the deterministic part of the fifth international planning competition (IPC5), presenting the language and benchmark domains that we developed for the competition, as well as a detailed experimental evaluation of the deterministic planners that entered IPC5, which helps to understand the state of the art in the field.We present an extension of pddl, called pddl3, allowing the user to express strong and soft constraints about the structure of the desired plans, as well as strong and soft problem goals. We discuss the expressive power of the new language focusing on the restricted version that was used in IPC5, for which we give some basic results about its compilability into pddl2. Moreover, we study the relative performance of the IPC5 planners in terms of solved problems, CPU time, and plan quality; we analyse their behaviour with respect to the winners of the previous competition; and we evaluate them in terms of their capability of dealing with soft goals and constraints, and of finding good quality plans in general. Overall, the results indicate significant progress in the field, but they also reveal that some important issues remain open and require further research, such as dealing with strong constraints and computing high quality plans in metric-time domains and domains involving soft goals or constraints.