Planning & Scheduling

RaySearch Demonstrates New Machine Learning Applications at ASTRO Artificial intelligence Latest Technology News


RaySearch exhibited its latest advances in oncology software at the 2018 American Society for Radiation Oncology (ASTRO) annual meeting, Oct. 21-24 in San Antonio, Texas, backed by machine learning and user-friendly tools to enable optimal use of clinical resources. The company showed its latest development in machine learning technology and automation in both its RayStation treatment planning system (TPS) and RayCare oncology information system (OIS). With its in-house machine learning department, RaySearch is currently developing machine learning and deep learning prototypes for areas such as treatment plan generation, organ segmentation and target volume estimation. RaySearch is also developing techniques for efficient large-scale data extraction and analysis. The first clinical applications of machine learning are automated treatment planning and automated organ segmentation and will be included in the next RayStation release in December.

Finite LTL Synthesis with Environment Assumptions and Quality Measures

AAAI Conferences

In this paper, we investigate the problem of synthesizing strategies for linear temporal logic (LTL) specifications that are interpreted over finite traces -- a problem that is central to the automated construction of controllers, robot programs, and business processes. We study a natural variant of the finite LTL synthesis problem in which strategy guarantees are predicated on specified environment behavior. We further explore a quantitative extension of LTL that supports specification of quality measures, utilizing it to synthesize high-quality strategies. We propose new notions of optimality and associated algorithms that yield strategies that best satisfy specified quality measures. Our algorithms utilize an automata-game approach, positioning them well for future implementation via existing state-of-the-art techniques.

A Novel Automata-Theoretic Approach to Timeline-Based Planning

AAAI Conferences

Timeline-based planning is a well-established approach successfully employed in a number of application domains.  A very restricted fragment, featuring only bounded temporal relations and token durations, is expressive enough to capture action-based temporal planning. As for computational complexity, it has been shown to be EXPSPACE-complete when unbounded temporal relations, but only bounded token durations, are allowed. In this paper, we present a novel automata-theoretic characterisation of timeline-based planning where the existence of a plan is shown to be equivalent to the nonemptiness of the language recognised by a nondeterministic finite-state  automaton that suitably encodes all the problem constraints (timelines and  synchronisation rules). Besides allowing us to restate known complexity results in a fairly natural and compact way, such an alternative characterisation makes it possible to finally establish the exact complexity of the full version of the problem with unbounded temporal relations and token durations, which was still open and turns out to be EXPSPACE-complete. Moreover, the proposed technique is general enough to cope with (infinite) recurrent goals, which received little attention so far, despite being quite common in real-word application scenarios.

Compiling Away Soft Trajectory Constraints in Planning

AAAI Conferences

Soft goals in planning are optional objectives that should be achieved in the terminal state. However, failing to achieve them does not result in the plan becoming invalid. State trajectory constraints are hard requirements towards the state trajectory of the plan. Soft trajectory constraints are a combination of both: soft preferences on how the hard goals are reached, i.e., optional requirements towards the state trajectory of the plan. Such a soft trajectory constraint may require that some fact should be always true, or should be true at some point during the plan. The quality of a plan is then measured by a metric which adds the sum of all action costs and a penalty for each failed soft trajectory constraint. Keyder and Geffner showed that soft goals can be compiled away. We generalize this approach and illustrate a method of compiling soft trajectory constraints into conditional effects and state dependent action costs using LTLf and deterministic finite automata. We provide two compilation schemes, with and without reward shaping, by rewarding and penalizing different states in the plan. With this we are able to handle such soft trajectory constraints without the need of altering the search algorithm or heuristics, using classical planners.

Heuristic Search Planning With Multi-Objective Probabilistic LTL Constraints

AAAI Conferences

We present an algorithm for computing cost-optimal stochastic policies for Stochastic Shortest Path problems (SSPs) subject to multi-objective PLTL constraints, i.e., conjunctions of probabilistic LTL formulas. Established algorithms capable of solving this problem typically stem from the area of probabilistic verification, and struggle with the large state spaces and constraint types found in automated planning. Our approach differs in two crucial ways. Firstly it operates entirely on-the-fly, bypassing the expensive construction of Rabin automata for the formulas and their prohibitive prior synchronisation with the full state space of the SSP. Secondly, it extends recent heuristic search algorithms and admissible heuristics for cost-constrained SSPs, to enable pruning regions made infeasible by the PLTL constraints. We prove our algorithm correct and optimal, and demonstrate encouraging scalability results.

Learning Classical Planning Strategies with Policy Gradient Artificial Intelligence

A common paradigm in classical planning is heuristic forward search. Forward search planners often rely on relatively simple best-first search algorithm, which remains fixed throughout the search process. In this paper, we introduce a novel search framework capable of alternating between several forward search approaches while solving a particular planning problem. Selection of the approach is performed using a trainable stochastic policy. This enables tailoring the search strategy to a particular distribution of planning problems and a selected performance metric, such as the IPC score or running time. We construct a strategy space using five search algorithms and a two-dimensional representation of the planner's state. Strategies are then trained on randomly generated planning problems using policy gradient. Experimental results show that the learner is able to discover domain-specific search strategies, thus improving the planner's performance with respect to the chosen metric.

Mean-based Heuristic Search for Real-Time Planning Artificial Intelligence

In this paper, we introduce a new heuristic search algorithm based on mean values for real-time planning, called MHSP. It consists in associating the principles of UCT, a bandit-based algorithm which gave very good results in computer games, and especially in Computer Go, with heuristic search in order to obtain a real-time planner in the context of classical planning. MHSP is evaluated on different planning problems and compared to existing algorithms performing on-line search and learning. Besides, our results highlight the capacity of MHSP to return plans in a real-time manner which tend to an optimal plan over the time which is faster and of better quality compared to existing algorithms in the literature.

Mining useful Macro-actions in Planning Artificial Intelligence

Abstract--Planning has achieved significant progress in recent years. Among the various approaches to scale up plan synthesis, the use of macro-actions has been widely explored. As a first stage towards the development of a solution to learn online macro-actions, we propose an algorithm to identify useful macroactions based on data mining techniques. The integration in the planning search of these learned macro-actions shows significant improvements over six classical planning benchmarks. Automated planning is an area of Artificial Intelligence that comes up with the challenge of devising systems that can autonomously find a plan to reach a set of goals. In classical planning, a problem is composed of an initial state, a goal specification and a set of actions.

Une approche totalement instanci\'ee pour la planification HTN Artificial Intelligence

Many planning techniques have been developed to allow autonomous systems to act and make decisions based on their perceptions of the environment. Among these techniques, HTN ({\it Hierarchical Task Network}) planning is one of the most used in practice. Unlike classical approaches of planning. HTN operates by decomposing task into sub-tasks until each of these sub-tasks can be achieved an action. This hierarchical representation provide a richer representation of planning problems and allows to better guide the plan search and provides more knowledge to the underlying algorithms. In this paper, we propose a new approach of HTN planning in which, as in conventional planning, we instantiate all planning operators before starting the search process. This approach has proven its effectiveness in classical planning and is necessary for the development of effective heuristics and encoding planning problems in other formalism such as CSP or SAT. The instantiation is actually used by most modern planners but has never been applied in an HTN based planning framework. We present in this article a generic instantiation algorithm which implements many simplification techniques to reduce the process complexity inspired from those used in classical planning. Finally we present some results obtained from an experimentation on a range of problems used in the international planning competitions with a modified version of SHOP planner using fully instantiated problems.

Planification en temps r\'eel avec agenda de buts et sauts Artificial Intelligence

In the context of real-time planning, this paper investigates the contributions of two enhancements for selecting actions. First, the agenda-driven planning enhancement ranks relevant atomic goals and solves them incrementally in a best-first manner. Second, the committed jump enhancement commits a sequence of actions to be executed at the following time steps. To assess these two enhancements, we developed a real-time planning algorithm in which action selection can be driven by a goal-agenda, and committed jumps can be done. Experimental results, performed on classical planning problems, show that agenda-planning and committed jumps are clear advantages in the real-time context. Used simultaneously, they enable the planner to be several orders of magnitude faster and solution plans to be shorter.