This paper is concerned with local search methods to solve job shop scheduling problems with uncertain durations modelled as fuzzy numbers. Based on a neighbourhood structure from the literature, a reduced set of moves and the consequent structure are defined. Theoretical results show that the proposed neighbourhood contains all the improving solutions from the original neighbourhood and provide a sufficient condition for optimality. Additionally, a makespan lower bound is proposed which can be used to discard neighbours. Experimental results illustrate the good performance of both proposals, which considerably reduce the computational load of the local search, as well as a synergy effect when they are simultaneously used.

A planning problem is k- dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is well-founded since k is a constant for all but a few of the standard planning domains, and is known to have implications for tractability. In this paper, we present several new complexity results for P ( k ), the class of k- dependent planning problems with binary variables and polytree causal graphs. The problem of plan generation for P ( k ) is equivalent to determining how many times each variable can change. Using this fact, we present a polytime plan generation algorithm for P (2) and P (3). For constant k > 3, we introduce and use the notion of a cover to find conditions under which plan generation for P ( k ) is polynomial.

Planning systems for real-world applications need the ability to handle concurrency and numeric fluents. Nevertheless, the predominant approach to cope with concurrency followed by the most successful participants in the latest International Planning Competitions (IPC) is still to find a sequential plan that is rescheduled in a post-processing step. We present Temporal Fast Downward (TFD), a planning system for temporal problems that is capable of finding low-makespan plans by performing a heuristic search in a temporal search space. We show how the context-enhanced additive heuristic can be successfully used for temporal planning and how it can be extended to numeric fluents. TFD often produces plans of high quality and, evaluated according to the rating scheme of the last IPC, outperforms all state-of-the-art temporal planning systems.

In this paper we extend dynamic controllability of temporally-flexible plans to temporally-flexible reactive programs.  We consider three reactive programming language constructs whose behavior depends on runtime observations; conditional execution, iteration, and exception handling. Temporally-flexible reactive programs are distinguished from temporally-flexible plans in that program execution is conditioned on the runtime state of the world.  In addition, exceptions are thrown and caught at runtime in response to violated timing constraints, and handled exceptions are considered successful program executions.  Dynamic controllability corresponds to a guarantee that a program will execute to completion, despite runtime constraint violations and uncertainty in runtime state.  An algorithm is developed which frames the dynamic controllability problem as an AND/OR search tree over possible program executions.  A key advantage of this approach is the ability to enumerate only a subset of possible program executions that guarantees dynamic controllability, framed as an AND/OR solution subtree.

Solving real-world problems using symbolic planning often requires a simplified formulation of the original problem, since certain subproblems cannot be represented at all or only in a way leading to inefficiency. For example, manipulation planning may appear as a subproblem in a robotic planning context or a packing problem can be part of a logistics task. In this paper we propose an extension of PDDL for specifying semantic attachments. This allows the evaluation of grounded predicates as well as the change of fluents by externally specified functions. Furthermore, we describe a general schema of integrating semantic attachments into a forward-chaining planner and report on our experience of adding this extension to the planners FF and Temporal Fast Downward. Finally, we present some preliminary experiments using semantic attachments.

Systems subject to (continuous) physical effects and controlled by (discrete) digital equipments, are today very common. Thus, many realistic domains where planning is required are represented by hybrid systems , i.e., systems containing both discrete and continuous values, with possibly a nonlinear continuous dynamics. The PDDL+ language allows one to model these domains, however the current tools can generally handle only planning problems on (possibly hybrid) systems with linear dynamics. Therefore, universal planning applied to hybrid systems and, in general, to non-linear systems is completely out of scope for such tools. In this paper, we propose the use of explicit model checking-based techniques to solve universal planning problems on such hardly-approachable domains.

When modeling real-world decision-theoretic planning problems in the Markov decision process (MDP) framework, it is often impossible to obtain a completely accurate estimate of transition probabilities. For example, natural uncertainty arises in the transition specification due to elicitation of MDP transition models from an expert or data, or non-stationary transition distributions arising from insufficient state knowledge. In the interest of obtaining the most robust policy under transition uncertainty, the Markov Decision Process with Imprecise Transition Probabilities (MDP-IPs) has been introduced to model such scenarios. Unfortunately, while solutions to the MDP-IP are well-known, they require nonlinear optimization and are extremely time-consuming in practice. To address this deficiency, we propose efficient dynamic programming methods to exploit the structure of factored MDPIPs. Noting that the key computational bottleneck in the solution of MDP-IPs is the need to repeatedly solve nonlinear constrained optimization problems, we show how to target approximation techniques to drastically reduce the computational overhead of the nonlinear solver while producing bounded, approximately optimal solutions. Our results show up to two orders of magnitude speedup in comparison to traditional “flat” dynamic programming approaches and up to an order of magnitude speedup over the extension of factored MDP approximate value iteration techniques to MDP-IPs.

In this paper we look at the problem of composing services that export their behavior in terms of a transition system, characterizing the choices of actions given to a client at each point in time. The composition consists of synthesizing an orchestrator that coordinates the available services so as to mimic the desired target service asked by the client. Specifically, in this paper we study the "conformant form" of the problem, where available services are partially controllable and partially observable, and hence, the orchestrator has to make its decisions exploiting the observations made so far only. We give a sound and complete procedure to synthesize the orchestrator in such case, and characterize the computational complexity of the problem. The procedure is based on working with belief (or knowledge) states, a standard technique to tackle conformant planning. Moreover we show that, although in general unavoidable, the powerset construction at the base of the belief state approach can be delegated to the symbolic manipulations of the game-structure model checking tool (TLV), which can be used to efficiently implement the orchestrator synthesis procedure.

Topological value iteration (TVI) is an effective algorithm for solving Markov decision processes (MDPs) optimally, which (1) divides an MDP into strongly-connected components, and (2) solves these components sequentially. Yet, TVI's usefulness tends to degrade if an MDP has large components, because the cost of the division process isn't offset by gains during solution.  This paper presents a new algorithm to solve MDPs optimally, focused  topological value iteration (FTVI). FTVI addresses TVI's limitations by restricting its attention to connected components that are relevant for solving the MDP. Specifically, FTVI uses a small amount of heuristic search to eliminate provably sub-optimal actions; this pruning allows FTVI to find smaller connected components, thus running faster.  We demonstrate that our new algorithm outperforms TVI by an order of magnitude, averaged across several domains. Surprisingly, FTVI also significantly outperforms popular "heuristically-informed" MDP algorithms such as LAO*, LRTDP, and BRTDP in many domains, sometimes by as much as two orders of magnitude. Finally, we characterize the type of domains where FTVI excels — suggesting a way to an informed choice of solver.

The dispatcher uses the dispatchable form to quickly make dynamic scheduling decisions. As autonomous systems become more capable and common, However, developing flexible executives for plans with they will need to reason about complex tasks and robustly choices, has been more difficult. Kim, Williams, and execute plans in uncertain environments. In previous work, Abramson present an executive called Kirk, which uses a Williams et al. introduced the Reactive Model-Based Programming deliberative planning step to change the execution sequence Language (RMPL), which is designed to allow online (2001). Although their results show improvement engineers to simply and intuitively express the desired behavior over prior planning systems, the latency is still too high for of the system (2003). Then the agent's executive determines tightly coupled systems, for example robots working with the correct sequence of actions to accomplish this humans or walking robots with fast dynamics. Recently, behavior, relieving the programmer of explicitly coding that Shah and Williams extended the compiler and dispatcher logic. RMPL programs often involve temporal constraints model to Temporal Constraint Satisfaction Problems (TCwhich the executives must reason over. SPs), a type of temporal problems with choice, by compactly Kim, Williams, and Abramson previously developed recording the possible set of solutions and efficiently Temporal Plan Networks (TPNs) as a temporal constraint reasoning over the possible options (2008).