A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints

Aerial robotics can be very useful to perform complex tasks in a distributed and cooperative fashion, such as localization of targets and search of point of interests (PoIs). In this work, we propose a distributed system of autonomous Unmanned Aerial Vehicles (UAVs), able to self-coordinate and cooperate in order to ensure both spatial and temporal coverage of specific time and spatial varying PoIs. In particular, we consider an UAVs system able to solve distributed dynamic scheduling problems, since each device is required to move towards a certain position in a certain time. We give a mathematical formulation of the problem as a multi-criteria optimization model, in which the total distances traveled by the UAVs (to be minimized), the customer satisfaction (to be maximized) and the number of used UAVs (to be minimized) are considered simultaneously. A dynamic variant of the basic optimization model, defined by considering the rolling horizon concept, is shown. We introduce a case study as an application scenario, where sport actions of a football match are filmed through a distributed UAVs system. The customer satisfaction and the traveled distance are used as performance parameters to evaluate the proposed approaches on the considered scenario.     

Performance prediction of an unmanned airborne vehicle multi-agent system

Consider unmanned airborne vehicle (UAV) control agents in a dynamic multi-agent system. The agents must have a set of goals such as destination airport and intermediate positions. At the same time, the agents have to avoid gun shootings which move to their neighbors randomly. Agents try to build and execute plans that yield a high probability of successfully achieving the targets. The plans are developed based on the negotiations between different UAVs in the region with the overall goal in mind. The information about enemy defenses can be communicated between UAVs and they can negotiate about the paths to be taken based on their resources, such as fuel, load, available time to complete the task and the information about the threat. By constructing a Markov Decision Process (MDP) in this paper, we derive the optimal path. Combining the MDP and the sample path technique, we obtain the maximum probability that the UAVs successfully reach the target.     

Modelling the mobile target covering problem using flying drones

This paper addresses the mobile targets covering problem by using unmanned aerial vehicles (UAVs). It is assumed that each UAV has a limited initial energy and the energy consumption is related to the UAV’s altitude. Indeed, the higher the altitude, the larger the monitored area and the higher the energy consumption. When an UAV runs out of battery, it is replaced by a new one. The aim is to locate UAVs in order to cover the piece of plane in which the target moves by using a minimum number of UAVs. Each target has to be monitored for each instant time. The problem under consideration is mathematically represented by defining mixed integer non-linear optimization models. Heuristic procedures are defined and they are based on restricted mixed integer programming (MIP) formulation of the problem. A computational study is carried out to assess the behaviour of the proposed models and MIP-based heuristics. A comparison in terms of efficiency and effectiveness among models and heuristics is carried out.     

A truck and drones model for last-mile delivery: A mathematical model and heuristic approach

We present a mathematical formulation and a heuristic solution approach for the optimal planning of delivery routes in a multi-modal system combining truck and Unmanned Aerial Vehicle (UAV) operations. In this system, truck and UAV operations are synchronized, i.e., one or more UAVs travel on a truck, which serves as a mobile depot. Deliveries can be made by both UAVs and the truck. While the truck follows a multi-stop route, each UAV delivers a single shipment per dispatch. The presented optimization model minimizes the waiting time of customers in the system. The model determines the optimal allocation of customers to truck and UAVs, the optimal route sequence of the truck, and the optimal launch and reconvene locations of the UAVs along the truck route. We formulate the problem as a Mixed-Integer Linear Programming (MILP) model and conduct a bound analysis to gauge the maximum potential of the proposed system to reduce customer waiting time compared to a traditional truck-only delivery system. To be able to solve real-world problem size instances, we propose an efficient Truck and Drone Routing Algorithm (TDRA). The solution quality and computational performance of the mathematical model and the TDRA are compared together and with the truck-only model based on a variety of problem instances. Further, we apply the TDRA to a real-world case study for e-commerce delivery in São Paulo, Brazil. Our numerical results suggest significant reductions in customer waiting time to be gained from the proposed multi-modal delivery model.     

Multiple UAVs path planning algorithms: a comparative study

Unmanned aerial vehicles (UAVs) are used in team for detecting targets and keeping them in its sensor range. There are various algorithms available for searching and monitoring targets. The complexity of the search algorithm increases if the number of nodes is increased. This paper focuses on multi UAVs path planning and Path Finding algorithms. Number of Path Finding and Search algorithms was applied to various environments, and their performance compared. The number of searches and also the computation time increases as the number of nodes increases. The various algorithms studied are Dijkstra’s algorithm, Bellman Ford’s algorithm, Floyd-Warshall’s algorithm and the AStar algorithm. These search algorithms were compared. The results show that the AStar algorithm performed better than the other search algorithms. These path finding algorithms were compared so that a path for communication can be established and monitored.     

Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches

In this paper, we consider a task allocation model that consists of assigning a set of m unmanned aerial vehicles (UAVs) to a set of n tasks in an optimal way. The optimality is quantified by target scores. The mission is to maximize the target score while satisfying capacity constraints of both the UAVs and the tasks. This problem is known to be NP-hard. Existing algorithms are not suitable for the large scale setting. Scalability and robustness are recognized as two main issues. We deal with these issues by two optimization approaches. The first approach is the Cross-Entropy (CE) method, a generic and practical tool of stochastic optimization for solving NP-hard problem. The second one is Branch and Bound algorithm, an efficient classical tool of global deterministic optimization. The numerical results show the efficiency of our approaches, in particular the CE method for very large scale setting.     

The availability of unmanned air vehicles: a post-case study

An Unmanned Air Vehicle (UAV) is an unmanned, remotely controlled, small air vehicle. It has an important role in anti-surface warfare. This implies over-the-horizon detection, classification, targeting and battle damage assessment. To perform these tasks several UAVs are needed to assist or interchange with each other. An important problem is to determine how many UAVs are needed in this respect. The answer depends on the characteristics of the UAV and its mission. The UAV availability problem is very complex and the usual method to solve such a problem is simulation. A disadvantage of simulation is that it can be very time-consuming. Hence it is not very suitable for sensitivity analysis. Moreover, since simulation gives mere approximations and is not very generic, theoretical insights are hardly gained. In this paper we show how such a complex problem can still be tackled analytically by using a basic model from reliability theory, viz., a 1-out-of-n system with cold standby, ample repair facility and general life time and repair distributions.     

Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms

A problem of assigning multiple agents to simultaneously perform cooperative tasks on consecutive targets is posed as a new combinatorial optimization problem. The investigated scenario consists of multiple ground moving targets prosecuted by a team of unmanned aerial vehicles (UAVs). The team of agents is heterogeneous, with each UAV carrying designated sensors and all but one carry weapons as well. To successfully prosecute each target it needs to be simultaneously tracked by two UAVs and attacked by a third UAV carrying a weapon. Only for small-sized scenarios involving not more than a few vehicles and targets the problem can be solved in sufficient time using classical combinatorial optimization methods. For larger-sized scenarios the problem cannot be solved in sufficient time using these methods due to timing constraints on the simultaneous tasks and the coupling between task assignment and path planning for each UAV. A genetic algorithm (GA) is proposed for efficiently searching the space of feasible solutions. A matrix representation of the chromosomes simplifies the encoding process and the application of the genetic operators. To further simplify the encoding, the chromosome is composed of sets of multiple genes, each corresponding to the entire set of simultaneous assignments on each target. Simulation results show the viability of the proposed assignment algorithm for different sized scenarios. The sensitivity of the performance to variations in the GA tuning parameters is also investigated.     

Active Disturbance Rejection Control of Quadrotor UAVs Based on Joint Observation and Feedforward Compensation北大核心CSCD

为解决模型参数不确定与外界干扰影响下,四旋翼无人机飞控作业中姿态与轨迹跟踪精度下降,反应迟缓的问题,利用拓展Kalman滤波应对非线性系统问题出色的适应能力和噪声抑制能力,对四旋翼状态信息进行初步估算来抑制高频信号干扰,从而降低了扩张状态观测器的估计负担.同时,与扩张状态观测器联合估计由系统不确定性参数与外界扰动联合组成的“总扰动”,使系统对于精确模型的依赖性降低,并利用扰动估计的微分值进行前馈补偿,以提高对突变扰动的跟踪精度,克服了突变干扰下的相位滞后现象.综合联合观测器、带前馈补偿的LESO及带误差补偿的PD控制律,形成了一种利用拓展Kalman滤波与前馈补偿后的扩张状态观测器联合观测扰动,能较大程度抑制高频噪声和突变扰动的改进型自抗扰控制器.仿真与实验结果表明,联合观测器能有效地减小观测误差幅值且能超前校正观测相位滞后,从而更好地得到更精确的状态信息,改进型自抗扰控制器能更好地满足四旋翼飞行器快速反应、高效稳定的控制要求,精准高效地完成复杂轨迹跟踪.     

多无人机协同规划的数学建模

针对第十三届全国研究生数学建模竞赛A题的多无人机协同规划问题展开研究.首先建立大路径和小路径的最短路径模型完成对十个目标群的扫描任务,其在雷达范围内航行总时间为10.37小时.然后建立实时自适应无人机作战模型针对未知远程雷达在不同情况下制定三级无人机作战策略,仿真结果显示:攻击方无人机滞留防御方雷达有效探测范围内的时间总和为8.81h.     

Devising a quick-running heuristic for an unmanned aerial vehicle (UAV) routing system

UAVs provide reconnaissance support for the US military and often need operational routes immediately; current practice involves manual route calculation that can involve hundreds of targets and a complex set of operational restrictions. Our research focused on providing an operational UAV routing system. This system required development of a reasonably effective, quick running routing heuristic. We present the statistical methodology used to devise a quick-running routing heuristic that provides reasonable solutions. We consider three candidate local search heuristic approaches, conduct an empirical analysis to parameterize each heuristic, competitively test each candidate heuristic, and provide statistical analysis on the performance of each candidate heuristic to include comparison of the results of the best candidate heuristic against a compilation of the best-known solutions for standard test problems. Our heuristic is a component of the final UAV routing system and provides the UAV operators a tool to perform their route development tasks quickly and efficiently.     

Close formation flight of swarm unmanned aerial vehicles via metric-distance brain storm optimization

Close formation flight of swarm unmanned aerial vehicles (UAVs) has drawn much attention from scholars due to its significant importance in many aspects. In this paper, we focus on an advanced controller design for swarm UAV close formation based on a novel bio-inspired algorithm, i.e., metric-distance brain storm optimization (MDBSO). The proposed method utilizes the brain storm optimization (BSO) which has been extensively adopted in complicated systems with great performances and modifies its basic operators to formulate the formation flight controller design. The original clustering operator in BSO is replaced by a fresh clustering method based on metric distances, while the individual updating operator utilizes Lévy distribution to extend search steps to fit into the metric searching regions. Then the proposed algorithm is applied to optimize the benchmark controller in swarm UAV close formation to enhance the tracking performances under complicated circumstances. Simulation results demonstrate that our approach is more superior in stable configuration of swarm UAV close formations by comparing with several generic methods.     

Online stochastic UAV mission planning with time windows and time-sensitive targets

In this paper we simultaneously consider three extensions to the standard Orienteering Problem (OP) to model characteristics that are of practical relevance in planning reconnaissance missions of Unmanned Aerial Vehicles (UAVs). First, travel and recording times are uncertain. Secondly, the information about each target can only be obtained within a predefined time window. Due to the travel and recording time uncertainty, it is also uncertain whether a target can be reached before the end of its time window. Finally, we consider the appearance of new targets during the flight, so-called time-sensitive targets, which need to be visited immediately if possible. We tackle this online stochastic UAV mission planning problem with time windows and time-sensitive targets using a re-planning approach. To this end, we introduce the Maximum Coverage Stochastic Orienteering Problem with Time Windows (MCS-OPTW). It aims at constructing a tour with maximum expected profit of targets that were already known before the flight. Secondly, it directs the planned tour to predefined areas where time-sensitive targets are expected to appear. We have developed a fast heuristic that can be used to re-plan the tour, each time before leaving a target. In our computational experiments we illustrate the benefits of the MCS-OPTW planning approach with respect to balancing the two objectives: the expected profits of foreseen targets, and expected percentage of time-sensitive targets reached on time. We compare it to a deterministic planning approach and show how it deals with uncertainty in travel and recording times and the appearance of time-sensitive targets.     

Adaptive-Repetitive Visual-Servo Control of Low-Flying Aerial Robots via Uncalibrated High-Flying Cameras

This paper presents the design and implementation of an adaptive-repetitive visual-servo control system for a moving high-flying vehicle (HFV) with an uncalibrated camera to monitor, track, and precisely control the movements of a low-flying vehicle (LFV) or mobile ground robot. Applications of this control strategy include the use of high-flying unmanned aerial vehicles (UAVs) with computer vision for monitoring, controlling, and coordinating the movements of lower altitude agents in areas, for example, where GPS signals may be unreliable or nonexistent. When deployed, a remote operator of the HFV defines the desired trajectory for the LFV in the HFV’s camera frame. Due to the circular motion of the HFV, the resulting motion trajectory of the LFV in the image frame can be periodic in time, thus an adaptive-repetitive control system is exploited for regulation and/or trajectory tracking. The adaptive control law is able to handle uncertainties in the camera’s intrinsic and extrinsic parameters. The design and stability analysis of the closed-loop control system is presented, where Lyapunov stability is shown. Simulation and experimental results are presented to demonstrate the effectiveness of the method for controlling the movement of a low-flying quadcopter, demonstrating the capabilities of the visual-servo control system for localization (i.e.,, motion capturing) and trajectory tracking control. In fact, results show that the LFV can be commanded to hover in place as well as track a user-defined flower-shaped closed trajectory, while the HFV and camera system circulates above with constant angular velocity. On average, the proposed adaptive-repetitive visual-servo control system reduces the average RMS tracking error by over 77% in the image plane and over 71% in the world frame compared to using just the adaptive visual-servo control law.     

Optimal placement of UV-based communications relay nodes

We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.     

Foreword to the Special Focus on Mathematics,Data and Knowledge

There is a growing interest in applying mathematical theories and methods from topology, computational geometry, differential equations, fluid dynamics, quantum statistics, etc. to describe and to analyze scientific regularities of diverse, massive, complex, nonlinear, and fast changing data accumulated continuously around the world and in discovering and revealing valid, insightful, and valuable knowledge that data imply. With increasingly solid mathematical foundations, various methods and techniques have been studied and developed for data mining, modeling, and processing, and knowledge representation, organization, and verification; different systems and mechanisms have been designed to perform data-intensive tasks in many application fields for classification, predication, recommendation, ranking, filtering, etc. This special focus of Mathematics in Computer Science is organized to stimulate original research on the interaction of mathematics with data and knowledge, in particular the exploration of new mathematical theories and methodologies for data modeling and analysis and knowledge discovery and management, the study of mathematical models of big data and complex knowledge, and the development of novel solutions and strategies to enhance the performance of existing systems and mechanisms for data and knowledge processing. The present foreword provides a short review of some key ideas and techniques on how mathematics interacts with data and knowledge, together with a few selected research directions and problems and a brief introduction to the four papers published in the focus.     

复杂非线性系统的控制综合与动态分析

随着当代科学和技术的发展,复杂非线性系统和控制理论研究不断深入,应用领域不断扩大,已影响了科技和社会领域的许多方面.针对当今该领域的研究难点和重点,本文集中讨论了复杂非线性系统控制研究中的3个关键问题,包括非光滑系统控制、网络化系统控制、临界态分析与控制.一方面是对在相关研究领域中的部分科研成果做一个简要的总结;另一方面,想借此机会在自动化学会控制理论专业委员会成立50周年之际向专业委员会表示感谢和祝贺.     

Making Statistics Significant in a Short Course for Graduates with Widely-Varying Non-Statistical Backgrounds

With reference to a short compulsory module for MBA students, this paper discusses how, despite a range of pressures and an extraordinary range of student backgrounds, fears and motivations, it is possible to quickly facilitate understanding and confidence in handling data and basic statistics for graduates in business and associated workplaces. Links and contrasts with a variety of undergraduate teaching scenarios help to enrich teaching and learning strategies, and the strategies and materials developed through interaction with the range of MBA students are transferable to other postgraduate coursework situations. In particular, the need for understanding and confidence in handling data and its presentation, in considering categorical and simple continuous data, and in understanding correlation and association, are common across many different workplaces and applications.