A therapy planning architecture that combines decision theory and artificial intelligence techniques

Through our experience with the ONCOCIN cancer therapy consultation system, we have identified a set of medical planning problems to which no single existing computer-based reasoning technique readily applies. In response to the need for automated assistance with this class of problems, we have devised a computer program called ONYX that combines decision-theoretic and artificial intelligence approaches to planning. We discuss our rationale for devising a new planning architecture and describe in detail how that architecture is implemented. The program's planning process consists of three steps: (i) the use of rules derived from therapy planning strategies to generate a small set of plausible plans, (ii) the use of knowledge about the structure and behavior of the human body to create simulations that predict possible consequences of each plan for the patient, and (iii) the use of decision theory to rank the plans according to how well the results of each simulation meet the treatment goals. This architecture explicitly manages the uncertainty inherent in many planning tasks, introduces a possible mechanism for the dissemination of decision-theoretic therapy advice, and potentially increases the number of problem solving domains in which expert system techniques can be effectively applied.     

Planning for tourism routes using social networks

Traveling recommendation systems have become very popular applications for organizing and planning tourist trips. Among other challenges, these applications are faced with the task of maintaining updated information about popular tourist destinations, as well as providing useful tourist guides that meet the users preferences. In this work we present the PlanTour, a system that creates personalized tourist plans using the human-generated information gathered from the minube¹ traveling social network. The system follows an automated planning approach to generate a multiple-day plan with the most relevant points of interest of the city/region being visited. Particularly, the system collects information of users and points of interest from minube, groups these points with clustering techniques to split the problem into per-day sub-problems. Then, it uses an off-the-shelf domain-independent automated planner that finds good quality tourist plans. Unlike other tourist recommender systems, the PlanTour planner is able to organize relevant points of interest taking into account user’s expected drives, and user scores from a real social network. The paper also highlights how to use human provided recommendations to guide the search for solutions of combinatorial tasks. The resulting intelligent system opens new possibilities of combining human-generated knowledge with efficient automated techniques when solving hard computational tasks. From an engineering perspective we advocate for the use of declarative representations of problem solving tasks that have been shown to improve modeling and maintenance of intelligent systems.     

A comparison of optimization techniques for AUV path planning in environments with ocean currents

To date, a large number of optimization algorithms have been presented for Autonomous Underwater Vehicle (AUV) path planning. However, little effort has been devoted to compare these techniques. In this paper, an quantum-behaved particle swarm optimization (QPSO) algorithm is introduced for solving the optimal path planning problem of an AUV operating in environments with ocean currents. An extensive study of the most important optimization techniques applied to optimize the trajectory for an AUV in several test scenarios is presented. Extensive Monte Carlo trials were also run to analyse the performance of these optimization techniques based on solution quality and stability. The weaknesses and strengths of each technique have been stated and the most appropriate algorithm for AUV path planning has been determined.     

Test Case Generation as an AI Planning Problem

While Artificial Intelligence techniques have been applied to a variety of software engineering applications, the area of automated software testing remains largely unexplored. Yet, test cases for certain types of systems (e.g., those with command language interfaces and transaction based systems) are similar to plans. We have exploited this similarity by constructing an automated test case generator with an AI planning system at its core. We compared the functionality and output of two systems, one based on Software Engineering techniques and the other on planning, for a real application: the StorageTek robot tape library command language. From this, we showed that AI planning is a viable technique for test case generation and that the two approaches are complementary in their capabilities.     

Automated planning for robotic layup of composite prepreg

Hand layup is a commonly used process for making composite structures from several plies of carbon-fiber prepreg. The process involves multiple human operators manipulating and conforming layers of prepreg to a mold. The manual layup process is ergonomically challenging, tedious, and limits throughput. Moreover, different operators may perform the process differently, and hence introduce inconsistency. We have developed a multi-robot cell to automate the layup process. A human expert provides a sequence to conform to the ply and types of end-effectors to be used as input to the system. The system automatically generates trajectories for the robots that can achieve the specified layup. Using the cell requires the automated generation of different types of plans. This paper addresses two main planning problems: (a) generating plans to grasp and manipulate the ply and (b) generating feasible robot trajectories. We use a hybrid-physics based simulator coupled with a state space search to find grasp plans. The system employs a strategy that applies constraints successively in a non-linear optimization formulation to identify suitable placements of the robots around the mold so that feasible trajectories can be generated. Our system can generate plans in a computationally efficient manner, and it can handle a wide variety of complex parts. We demonstrate the automated layup by conducting physical experiments on an industry-inspired mold using the generated plans.     

An automated bi-level optimization approach for IMRT

Intensity-modulated radiation therapy is used worldwide to treat cancer patients. The objective of this treatment is to deliver a prescribed radiation dose to the tumor while sparing, as much as possible, all the healthy tissues, especially organs at risk (OAR). This means that the planning of a radiotherapy treatment should take into consideration conflicting objectives: to be able to spare as much as possible the OAR guaranteeing, at the same time, that the desired radiation is delivered to the volumes to treat. While the volumes to treat can be adequately irradiated from almost any set of directions, the radiation directions that are chosen have a determinant impact on the OAR. This means that those directions that provide an improved OAR sparing should be selected. The choice of radiation directions (beam angles) can thus be interpreted as being fundamentally determined by the OAR, with the radiation intensities associated with each of these directions being determined by the needed radiation to be delivered to the volumes to treat. In this work, we interpret the radiotherapy treatment planning problem as a bi-level optimization problem. At the upper level, OAR control the choice of the beam angles, which are selected aiming at OAR sparing. At the lower level, the optimal radiation intensities are decided by the volumes to treat, considering the beam angle ensemble obtained at the upper level. The proposed bi-level approach was tested using 10 clinical head-and-neck cancer cases already treated at the Portuguese Institute of Oncology in Coimbra.     

机器人操作臂奇异路径约束最优轨迹规划

路径约束最优轨迹规划的关键是引入标量路径参数来降低优化问题的维数 ．当路径穿越奇异点时，由于关节位移难以表示为任务空间路径参数的解析函数，给常规的 路径参数化方法带来困难．本文引入一种新的参数化方法，采用路径跟踪方程解曲线的弧长 为参数，解决了奇异点邻域的路径跟踪问题，把奇异路径轨迹规划转化为常规规划问题，并 采用动态规划方法求解轨迹规划问题．仿真表明，本文提出的参数化方法与动态规划结合起 来，是解决奇异路径最优轨迹规划的有效途径．      

Integrating human observer inferences into robot motion planning

Our goal is to enable robots to produce motion that is suitable for human–robot collaboration and co-existence. Most motion in robotics is purely functional, ideal when the robot is performing a task in isolation. In collaboration, however, the robot’s motion has an observer, watching and interpreting the motion. In this work, we move beyond functional motion, and introduce the notion of an observer into motion planning, so that robots can generate motion that is mindful of how it will be interpreted by a human collaborator. We formalize predictability and legibility as properties of motion that naturally arise from the inferences in opposing directions that the observer makes, drawing on action interpretation theory in psychology. We propose models for these inferences based on the principle of rational action, and derive constrained functional trajectory optimization techniques for planning motion that is predictable or legible. Finally, we present experiments that test our work on novice users, and discuss the remaining challenges in enabling robots to generate such motion online in complex situations.     

Trajectory optimization and state selection for urban automated driving

The automated driving is an emerging technology in which a car performs recognition, decision making, and control. The decision-making system consists of route planning and trajectory planning. The route planning optimizes the shortest path to the destination like an automotive navigation system. According to static and dynamic obstacles around the vehicle, the trajectory planning generates lateral and longitudinal profiles for vehicle maneuver to drive the given path. This study is focused on the trajectory planning for vehicle maneuver in urban traffic scenes. This paper proposes a trajectory generation method that extends the existing method to generate more natural behavior with small acceleration and deceleration. This paper introduces an intermediate behavior to gradually switch from the velocity keeping to the distance keeping. The proposed method can generate smooth trajectory with small acceleration/deceleration. Numerical experiments show that the vehicle generates smooth behaviors according to surrounding vehicles.     

An approach to efficient planning with numerical fluents and multi-criteria plan quality

Dealing with numerical information is practically important in many real-world planning domains where the executability of an action can depend on certain numerical conditions, and the action effects can consume or renew some critical continuous resources, which in pddl can be represented by numerical fluents. When a planning problem involves numerical fluents, the quality of the solutions can be expressed by an objective function that can take different plan quality criteria into account.We propose an incremental approach to automated planning with numerical fluents and multi-criteria objective functions for pddl numerical planning problems. The techniques in this paper significantly extend the framework of planning with action graphs and local search implemented in the lpg planner. We define the numerical action graph (NA-graph) representation for numerical plans and we propose some new local search techniques using this representation, including a heuristic search neighborhood for NA-graphs, a heuristic evaluation function based on relaxed numerical plans, and an incremental method for plan quality optimization based on particular search restarts. Moreover, we analyze our approach through an extensive experimental study aimed at evaluating the importance of some specific techniques for the performance of the approach, and at analyzing its effectiveness in terms of fast computation of a valid plan and quality of the best plan that can be generated within a given CPU-time limit. Overall, the results show that our planner performs quite well compared to other state-of-the-art planners handling numerical fluents.     

Automation and optimization in crane lift planning: A critical review

Safe and efficient crane operations play a significant role in successful delivery of construction projects, and thus meticulous planning of crane lifts becomes increasingly critical. Crane lift planning involves a series of complex decisions to be made, while satisfying a wide range of criteria and constraints. Conventionally, making these decisions is time-consuming and to a large extent relies on the planner’s experience. To make more informed and optimized planning decisions, past research works investigated various automated planning techniques and optimization algorithms. However, most studies focus on an individual planning decision or a particular lifting scenario, which makes the findings hard to be generalized. Thus, the knowledge in lift planning is rather fragmented and the state-of-the-art in lift planning is not explicitly presented. This study, therefore, aims to conduct a critical review and assessment on the literature on crane lift planning automation and optimization and to establish a solid foundation to inform future research. It first presents an overview of the literature in crane lift planning with respect to the planning decision and the type of cranes the studies focus on. Secondly, for each lift planning decision, the assumptions, objectives, decision variables, and constraints are formulated based on the literature and analyzed from the perspectives of problem formulation coherence. Furthermore, each problem-solving method is evaluated with regard to a tri-axial evaluation diagram to allow an in-depth discussion on the efficacy and practicality of planning results. Finally, based on the discussion and existing literature, a BIM-based lift planning framework is presented and future research directions are recommended to further improve the effectiveness and efficiency of lift planning practice.     

Reducing energy consumption through trajectory optimization for a metro network

The techniques of optimal control and optimization are applied to a practical problem of reducing energy consumed by the Montreal Metro (subway) system. The problem considered is the determination of tunnel trajectories in the "equivalent" vertical plane when trains traveling in both directions must follow the same trajectory. The problem is first formulated as a control problem with control and state constraints. Then, under certain simplifying assumptions, an heuristic method employing a direct search algorithm is presented and used in the trajectory optimization. The trajectories are optimized to reduce the sum of the energy consumed by the trains traveling in both directions on the trajectory. The results show an average reduction of 7.73 percent in energy consumption as compared with existing trajectories. The trajectories found using the method presented here will be followed in future tunnel construction.     

An online collision-free trajectory generation algorithm for human–robot collaboration

The premise of human–robot collaboration is that robots have adaptive trajectory planning strategies in hybrid work cell. The aim of this paper is to propose a new online collision avoidance trajectory planning algorithm for moderate dynamic environments to insure human safety when sharing collaborative tasks. The algorithm contains two parts: trajectory generation and local optimization. Firstly, based on empirical Dirichlet Process Gaussian Mixture Model (DPGMM) distribution learning, a neural network trajectory planner called Collaborative Waypoint Planning network (CWP-net) is proposed to generate all key waypoints required for dynamic obstacle avoidance in joint space according to environmental inputs. These points are used to generate quintic spline smooth motion trajectories with velocity and acceleration constraints. Secondly, we present an improved Stochastic Trajectory Optimization for Motion Planning (STOMP) algorithm which locally optimizes the generated trajectories of CWP-net by constraining the trajectory optimization range and direction through the DPGMM model. Simulations and real experiments from an industrial use case of human–robot collaboration in the field of aircraft assembly testing show that the proposed algorithm can smoothly adjust the nominal path online and effectively avoid collisions during the collaboration.     

Automated clustering of trajectory data using a particle swarm optimization

Clustering trajectory data discovers and visualizes available structure in movement patterns of mobile objects and has numerous potential applications in traffic control, urban planning, astronomy, and animal science. In this paper, an automated technique for clustering trajectory data using a Particle Swarm Optimization (PSO) approach has been proposed, and Dynamic Time Warping (DTW) distance as one of the most commonly-used distance measures for trajectory data is considered. The proposed technique is able to find (near) optimal number of clusters as well as (near) optimal cluster centers during the clustering process. To reduce the dimensionality of the search space and improve the performance of the proposed method (in terms of a certain performance index), a Discrete Cosine Transform (DCT) representation of cluster centers is considered. The proposed method is able to admit various cluster validity indexes as objective function for optimization. Experimental results over both synthetic and real-world datasets indicate the superiority of the proposed technique to fuzzy C-means, fuzzy K-medoids, and two evolutionary-based clustering techniques proposed in the literature.     

通用规划综述*

对智能规划中的通用规划思想及方法进行了全面综述。通用规划是对特定的规划领域制定通用的解形式,从而可以不通过搜索而直接得到具体规划问题的解。当搜索空间随着问题规模指数级增长时,人们希望通过归纳已有规划解的规律,以较小的代价来获取大规模问题的解。介绍了通用规划的基本思想和产生方法,讨论了其与相关工作的联系以及局限性,并给出了对其未来研究方向的展望。     

Computational enhancements to fluence map optimization for total marrow irradiation using IMRT

The fluence map optimization (FMO) problem is a core problem in intensity modulated radiation therapy (IMRT) treatment planning. Although it has been studied extensively for site-specific treatment planning, few studies have examined efficient computational methods for solving it for intensity modulated total marrow irradiation (IM-TMI) planning; few studies have also looked at exploiting prior beamlet information to solve the FMO problem in a beam orientation optimization context. In this study, we consider different types of line search strategies and different types of warm-start techniques to improve the speed with which the FMO problem for IM-TMI is solved and the quality of the end solution. We also consider a parallelism-enhanced algorithm to solve the FMO problem for IM-TMI treatment planning with a large number of beams (36 equispaced beams at each of 11 isocenters, for a total of 396 beams). We show that the backtracking line search strategy with step reduction exhibits the best performance and that using either of the two types of warm-start techniques which we consider leads to significant improvements in both solution time and quality. We also provide results for the aforementioned 396-beam plan and show that 30-beam solutions obtained using beam orientation optimization attain a comparable level of quality as this larger solution.     

An enhanced genetic algorithm for automated assembly planning

Automated assembly planning reduces manufacturing manpower requirements and helps simplify product assembly planning, by clearly defining input data, and input data format, needed to complete an assembly plan. In addition, automation provides the computational power needed to find optimal or near-optimal assembly plans, even for complex mechanical products. As a result, modern manufacturing systems use, to an ever greater extent, automated assembly planning rather than technician-scheduled assembly planning. Thus, many current research reports describe efforts to develop more efficient automated assembly planning algorithms. Genetic algorithms show particular promise for automated assembly planning. As a result, several recent research reports present assembly planners based upon traditional genetic algorithms. Although prior genetic assembly planners find improved assembly plans with some success, they also tend to converge prematurely at local-optimal solutions. Thus, we present an assembly planner, based upon an enhanced genetic algorithm, that demonstrates improved searching characteristics over an assembly planner based upon a traditional genetic algorithm. In particular, our planner finds optimal or near-optimal solutions more reliably and more quickly than an assembly planner that uses a traditional genetic algorithm.     

Fast and insightful bi-objective optimization for prostate cancer treatment planning with high-dose-rate brachytherapy

Purpose:Prostate high-dose-rate brachytherapy (HDR-BT) planning involves determining the movement that a high-strength radiation stepping source travels through the patient’s body, such that the resulting radiation dose distribution sufficiently covers tumor volumes and safely spares nearby healthy organs from radiation risks. The Multi-Objective Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (MO-RV-GOMEA) has been shown to be able to effectively handle this inherent bi-objective nature of HDR-BT planning. However, in clinical practice there is a very restricted planning time budget (often less than 1 h) for HDR-BT planning, and a considerable amount of running time needs to be spent before MO-RV-GOMEA finds a good trade-off front of treatment plans (about20–30 min on a single CPU core) with sufficiently accurate dose calculations, limiting the applicability of the approach in the clinic. To address this limitation, we propose an efficiency enhancement technique for MO-RV-GOMEA solving the bi-objective prostate HDR-BT planning problem.Methods:Dose-Volume (DV) indices are often used to assess the quality of HDR-BT plans. The accuracy of these indices depends on the number of dose calculation points at which radiation doses are computed. These are randomly uniformly sampled inside target volumes and organs at risk. In available HDR-BT planning optimization algorithms, the number of dose calculation points is fixed. The more points are used, the better the accuracy of the obtained results will be, but also the longer the algorithms need to be run. In this work, we introduce a so-called multi-resolution scheme that gradually increases the number of dose calculation points during the optimization run such that the running time can be substantially reduced without compromising on the accuracy of the obtained results.Results and conclusion:Experiments on a data set of 18 patient cases show that with the multi-resolution scheme, MO-RV-GOMEA can achieve a sufficiently good trade-off front of treatment plans after five minutes of running time on a single CPU core (4–6 times faster than the old approach with a fixed number of dose calculation points). When the optimization with the multi-resolution scheme is run on a quad-core machine, five minutes are enough to obtain trade-off fronts that are nearly as good as those obtained by running optimization with the old approach in one hour (i.e., 12 times faster). This leaves ample time to perform the selection of the preferred treatment plan from the trade-off front for the specific patient at hand. Furthermore, comparisons with real clinical treatment plans, which were manually made by experienced BT planners within 30–60 min, confirm that the plans obtained by our approach are superior in terms of DV indices. These results indicate that our proposed approach has the potential to be employed in clinical practice.     

Approximate dynamic programming for automated vacuum waste collection systems

The collection and treatment of waste poses a major challenge to modern urban planning, particularly to smart cities. To cope with this problem, a cost-effective alternative to conventional methods is the use of Automated Vacuum Waste Collection (AVWC) systems, using air suction on a closed network of underground pipes to transport waste from the drop off points scattered throughout the city to a central collection point. This paper describes and empirically evaluates a novel approach to defining daily operation plans for AVWC systems to improve quality of service, and reduce energy consumption, which represents about 60% of the total operation cost. We model a daily AVWC operation as a Markov decision process, and use Approximate Dynamic Programming techniques (ADP) to obtain optimal operation plans. The experiments, comparing our approach with the current approach implemented in some real-world AVWC systems, show that ADP techniques significantly improve the quality of AVWC operation plans.     

面向多目标侦察任务的无人机航线规划

针对无人机执行多目标侦察任务的航线规划问题,提出一种改进粒子群算法结合高斯伪谱法的分层航线规划方法.设计改进粒子群算法进行航线预规划,针对传统粒子群优化算法收敛速度慢、易陷入局部最优的问题,通过引入混沌映射初始化和自适应参数调整策略,加快算法收敛速度,提升解的最优性.在此基础上,结合最短路求解策略,完成对侦察任务的时序排列,得到可执行的最优侦察任务方案,进而为提升侦察航线的精确性和可控性,基于高斯伪谱法进行航线再规划.引入航线预规划结果作为初值猜测,进一步提升算法的效率和准确性.最后在复杂环境下进行无人机侦察航线仿真分析,结果表明所设计算法能够快速生成任务执行方案与高精度侦察航线,符合军事无人机执行侦察任务的工程应用.