Optimal search strategies using simultaneous generalized hill climbing algorithms

Optimal search strategies for conducting reconnaissance, surveillance or search and rescue operations with limited assets are of significant interest to military decision makers. Multiple search platforms with varying capabilities can be deployed individually or simultaneously for these operations (e.g., helicopters, fixed wing or satellite). Due to the timeliness required in these operations, efficient use of available search platforms is critical to the success of such missions. Designing optimal search strategies over multiple search platforms can be modeled and solved as a multiple traveling salesman problem (MTSP). This paper demonstrates how simultaneous generalized hill climbing algorithms (SGHC) can be used to determine optimal search strategies over multiple search platforms for the MTSP. Computational results with SGHC algorithms applied to the MTSP are reported. These results demonstrate that when limited computing budgets are available, optimal/near-optimal search strategies over multiple search platforms can be obtained more efficiently using SGHC algorithms compared to other generalized hill climbing algorithms. Applications and extensions of this research to other military applications are also discussed.     

Model-based and model-free control of flexible-link robots: A comparison between representative methods

The paper presents a comparative study on representative methods for model-based and model-free control of flexible-link robots. Model-based techniques for the control of flexible-link robots can come up against limitations when an accurate model is unavailable, due to parameters uncertainty or truncation of high order vibration modes. On the other hand, several research papers argue that suitable model-free control methods result in satisfactory performance of flexible-link robots. In this paper two model-free approaches of flexible-link robot control are examined: (i) energy-based control, and (ii) neural adaptive control. The performance of the aforementioned methods is compared to the inverse dynamics model-based control, in a simulation case study for planar 2-DOF manipulators.     

突发事件应急救援动态调度优化:以KX井喷事故为例

突发事件应急救援具有高度的不确定性和动态性。本文以KX井喷事故为例,研究突发事件应急救援的动态调度优化问题。作者首先给出KX井喷事故的背景资料,在此基础上提炼本文所研究的问题,即如何基于突发事件救援过程中的实际变化,对原定计划进行最优的动态调整。随后,构建突发事件应急救援的动态调度优化模型,针对其NP-hard属性设计专门的禁忌搜索启发式算法。最后,对KX井喷事故应急救援的动态调度问题进行求解,并结合现实情况对求解结果进行讨论分析,得到如下结论:早期发生的计划调整通常会对应急救援产生较大的影响,而后期发生的计划调整的影响则相对较小。本文的研究可为突发事件应急救援的实时指挥提供定量化决策支持。     

Modelling a hormone-inspired controller for individual- and multi-modular robotic systems

For all living organisms, the ability to regulate internal homeostasis is a crucial feature. This ability to control variables around a set point is found frequently in the physiological networks of single cells and of higher organisms. Also, nutrient allocation and task selection in social insect colonies can be interpreted as homeostatic processes of a super-organism. And finally, behaviour can also represent such a control scheme. We show how a simple model of hormone regulation, inspired by simple biological organisms, can be used as a novel method to control the behaviour of autonomous robots. We demonstrate the formulation of such an artificial homeostatic hormone system (AHHS) by a set of linked difference equations and explain how the homeostatic control of behaviour is achieved by homeostatic control of the internal ‘hormonal’ state of the robot. The first task that we used to check the quality of our AHHS controllers was a very simple one, which is often a core functionality in controller programmes that are used in autonomous robots: obstacle avoidance. We demonstrate two implementations of such an AHHS controller that performs this task in differing levels of quality. Both controllers use the concept of homeostatic control of internal variables (hormones) and they extend this concept to also include the outside world of the robots into the controlling feedback loops: As they try to regulate internal hormone levels, they are forced to keep a homeostatic control of sensor values in a way that the desired goal ‘obstacle avoidance’ is achieved. Thus, the created behaviour is also a manifestation of the acts of homeostatic control. The controllers were evaluated using a stock-and-flow model that allowed sensitivity analysis and stability tests. Afterwards, we have also tested both controllers in a multi-agent simulation tool, which allowed us to predict the robots' behaviours in various habitats and group sizes. Finally, we demonstrate how this novel AHHS controller is suitable to control a multi-cellular robotic organism in an evolutionary robotics approach, which is used for self-programming in a gait-learning task. These examples shown in this article represent the first step in our research towards autonomous aggregation and coordination of robots to higher-level modular robotic organisms that consist of several joined autonomous robotic units. Finally, we plan to achieve such aggregation patterns and to control complex-shaped robotic organisms using AHHS controllers, as they are described here.     

A sequential integer programming method for discontinuous labor tour scheduling

General set-covering formulations (GSCFs) of labor tour scheduling problems have recently received substantial attention in the research literature. The most successful heuristic approaches to these problems have used the linear programming (LP) solution to the GSCF as a starting point and subsequently applied heuristic augmentation and improvement procedures to obtain feasible integer solutions. Integer programming (IP) methods eliminate the need for augmentation and improvement procedures, but have generally been considered intractable for large GSCFs. In this paper we present a sequential mixed-integer programming (SMIP) heuristic for discontinuous (< 24 hours/day) tour-scheduling problems which takes advantage of the structure of the GSCF. The new heuristic substantially outperformed two prominent LP-based methods across 432 full-time workforce test problems, yielding optimal solutions for 429 of the problems. For a set of 36 test problems associated with a mixed-workforce scheduling environment that allowed both full-time and part-time employees with varying levels of cost and productivity, the SMIP heuristic yielded solution costs that were significantly better than previously published costs obtained with competitive methods.     

Two‐stage algorithms for covering array construction

Modern software systems often consist of many different components, each with a number of options. Although unit tests may reveal faulty options for individual components, functionally correct components may interact in unforeseen ways to cause a fault. Covering arrays are used to test for interactions among components systematically. A two‐stage framework, providing a number of concrete algorithms, is developed for the efficient construction of covering arrays. In the first stage, a time and memory efficient randomized algorithm covers most of the interactions. In the second stage, a more sophisticated search covers the remainder in relatively few tests. In this way, the storage limitations of the sophisticated search algorithms are avoided; hence, the range of the number of components for which the algorithm can be applied is extended, without increasing the number of tests. Many of the framework instantiations can be tuned to optimize a memory‐quality trade‐off, so that fewer tests can be achieved using more memory.     

Accurate and robust body position trajectory tracking of six-legged walking robots with nonsingular terminal sliding mode control method

Many tasks, such as walking in narrow environments, detecting land mines, coordinating with manipulators, and avoiding obstacles, demand multi-legged walking robots to accurately and robustly track predefined body trajectories. Tracking body position trajectory must be accurate and robust in these situations, but research on this topic is rarely carried out. In this study, we propose a nonsingular terminal sliding mode (NTSM) control algorithm to implement accurate and robust body position trajectory tracking of six-legged walking robots. The NTSM control algorithm is constructed on the basis of the body position trajectory tracking model with a new NTSM reaching law. The performance of the NTSM control method is evaluated through several verifications. Results demonstrate that the proposed algorithm is effective for accurate and robust body position trajectory tracking. The findings of this study can provide insights into improving multi-legged walking robots’ walking and operation abilities in special environments and expanding the application fields of these robots.     

Recursive Methods in Modeling and Control of Modular Robotic Systems

This paper addresses the dynamical modeling and control of reconfigurable modular robots. The modular actuators (brushless DC motors with Harmonic Drive gears) for the robots under consideration are connected by rigid links. This way the robot can be assembled in different configurations by rearranging these components. For dynamical modeling the Projection Equation in Subsystem representation is used, taking advantage of its modular structure. Due to the lack of position sensors at the gearbox output shaft, deflections caused by the elasticities in the gears can not be compensated by the PD motor joint controller. Therefore, a correction of the motor trajectory is needed, which can be calculated as part of a flatness based feed-forward control using the exact model of the robot. With the recursive approach proposed in this paper the concept of reconfigurability is retained. For validation a redundant articulated robot arm with seven joints is regarded and results are presented. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Cooperative Sensing and Distributed Control of a Diffusion Process Using Centroidal Voronoi Tessellations

<正>This paper considers how to use a group of robots to sense and control a diffusion process.The diffusion process is modeled by a partial differential equation (PDE),which is a both spatially and temporally variant system.The robots can serve as mobile sensors,actuators,or both.Centroidal Voronoi Tessellations based coverage control algorithm is proposed for the cooperative sensing task.For the diffusion control problem,this paper considers spraying control via a group of networked mobile robots equipped with chemical neutralizers,known as smart mobile sprayers or actuators,in a domain of interest having static mesh sensor network for concentration sensing.This paper also introduces the information sharing and consensus strategy when using centroidal Voronoi tessellations algorithm to control a diffusion process.The information is shared not only on where to spray but also on how much to spray among the mobile actuators.Benefits from using CVT and information consensus seeking for sensing and control of a diffusion process are demonstrated in simulation results.     

基于资源约束的突发事件应急救援鲁棒性调度优化

突发事件应急救援的调度优化,对于救援活动的顺利实施及应急资源的有效使用具有至关重要的作用。本文研究资源约束下的突发事件应急救援鲁棒性调度优化问题,其中,鲁棒性定义为各活动的时间缓冲与其权重系数乘积的总和,目标是在资源可用量及救援期限的约束下,安排活动开始时间和执行模式以最大化应急救援计划的鲁棒性。作者构建了问题的0-1规划优化模型,针对其NP-hard属性,基于问题特征设计双环路禁忌搜索启发式算法。通过对一个算例的计算分析,得到如下结论:给定网络结构及时间参数,利用权重系数的定义可以将时间缓冲分配到重要活动上,由此提高应急救援计划的鲁棒性;随着资源可用量的增加,计划的鲁棒性呈上升趋势,而当救援期限延长时,计划的鲁棒性单调增加。本文研究可为突发事件应急救援基准计划的制定提供决策支持。     

Elementary landscape decomposition of the 0-1 unconstrained quadratic optimization

Landscapes’ theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of an especial kind of landscape called elementary landscape. The elementary landscape decomposition of a combinatorial optimization problem is a useful tool for understanding the problem. Such decomposition provides an additional knowledge on the problem that can be exploited to explain the behavior of some existing algorithms when they are applied to the problem or to create new search methods for the problem. In this paper we analyze the 0-1 Unconstrained Quadratic Optimization from the point of view of landscapes’ theory. We prove that the problem can be written as the sum of two elementary components and we give the exact expressions for these components. We use the landscape decomposition to compute autocorrelation measures of the problem, and show some practical applications of the decomposition.     

双目标突发事件应急救援前摄性调度优化

本文以救援时间最短化与计划鲁棒性最大化为目标,研究突发事件应急救援前摄性调度优化问题。作者首先对所研究问题进行界定,其中计划鲁棒性定义为各活动开始时间可调整时差的总和,任务是在应急预算和救援期限的约束下,确定活动执行模式与开始时间以实现上述两个目标。随后,构建问题的0-1规划优化模型,鉴于其强NP-hard属性,设计禁忌搜索启发式算法。最后用一个算例对研究进行说明,得到如下结论:救援时间随应急预算的增加而缩短,随救援期限的放宽而延长;计划鲁棒性随应急预算的增加或救援期限的放宽而提高;当权重分配系数增大时,应急救援时间先保持不变而后缩短,计划鲁棒性则呈减小趋势。本文研究可为突发事件应急救援的组织与协调提供决策支持。     

Efficient reconfiguration of lattice-based modular robots

Modular robots consist of many identical units (or atoms) that can attach together and perform local motions. By combining such motions, one can achieve a reconfiguration of the global shape of a robot. The term modular comes from the idea of grouping together a fixed number of atoms into a metamodule, which behaves as a larger individual component. Recently, a fair amount of research has focused on algorithms for universal reconfiguration using Crystalline and Telecube metamodules, which use expanding/contracting cubical atoms.From an algorithmic perspective, this work has achieved some of the best asymptotic reconfiguration times under a variety of different physical models. In this paper we show that these results extend to other types of modular robots, thus establishing improved upper bounds on their reconfiguration times. We describe a generic class of modular robots, and we prove that any robot meeting the generic class requirements can simulate the operation of a Crystalline atom by forming a six-arm structure. Previous reconfiguration bounds thus transfer automatically by substituting the six-arm structures for the Crystalline atoms. We also discuss four prototyped robots that satisfy the generic class requirements: M-TRAN, SuperBot, Molecube, and RoomBot.     

Sparse Regression by Projection and Sparse Discriminant Analysis

Recent years have seen active developments of various penalized regression methods, such as LASSO and elastic net, to analyze high-dimensional data. In these approaches, the direction and length of the regression coefficients are determined simultaneously. Due to the introduction of penalties, the length of the estimates can be far from being optimal for accurate predictions. We introduce a new framework, regression by projection, and its sparse version to analyze high-dimensional data. The unique nature of this framework is that the directions of the regression coefficients are inferred first, and the lengths and the tuning parameters are determined by a cross-validation procedure to achieve the largest prediction accuracy. We provide a theoretical result for simultaneous model selection consistency and parameter estimation consistency of our method in high dimension. This new framework is then generalized such that it can be applied to principal components analysis, partial least squares, and canonical correlation analysis. We also adapt this framework for discriminant analysis. Compared with the existing methods, where there is relatively little control of the dependency among the sparse components, our method can control the relationships among the components. We present efficient algorithms and related theory for solving the sparse regression by projection problem. Based on extensive simulations and real data analysis, we demonstrate that our method achieves good predictive performance and variable selection in the regression setting, and the ability to control relationships between the sparse components leads to more accurate classification. In supplementary materials available online, the details of the algorithms and theoretical proofs, and R codes for all simulation studies are provided.     

A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic

Adaptive large neighborhood search (ALNS) is a useful framework for solving difficult combinatorial optimisation problems. As a metaheuristic, it consists of some components that must be tailored to the specific optimisation problem that is being solved, while other components are problem independent. The literature is sparse with respect to studies that aim to evaluate the relative merit of different alternatives for specific problem independent components. This paper investigates one such component, the move acceptance criterion in ALNS, and compares a range of alternatives. Through extensive computational testing, the alternative move acceptance criteria are ranked in three groups, depending on the performance of the resulting ALNS implementations. Among the best variants, we find versions of criteria based on simulated annealing, threshold acceptance, and record-to-record travel, with a version of the latter being consistently undominated by the others. Additional analyses focus on the search behavior, and multiple linear regression is used to identify characteristics of search behavior that are associated with good search performance.     

Evolving systems: Adaptive key component control and inheritance of passivity and dissipativity

We propose a new framework called Evolving Systems to describe the self-assembly, or autonomous assembly, of actively controlled dynamical subsystems into an Evolved System with a higher purpose. Autonomous assembly of large, complex flexible structures in space is a target application for Evolving Systems. A critical requirement for autonomous assembling structures is that they remain stable during and after assembly. The fundamental topic of inheritance of stability, dissipativity, and passivity in Evolving Systems is the primary focus of this research. In this paper, we develop an adaptive key component controller to restore stability in Nonlinear Evolving Systems that would otherwise fail to inherit the stability traits of their components. We provide sufficient conditions for the use of this novel control method and demonstrate its use on an illustrative example.     

A Bayesian approach to modeling lost person behaviors based on terrain features in Wilderness Search and Rescue

In Wilderness Search and Rescue (WiSAR), the incident commander (IC) creates a probability distribution map of the likely location of the missing person. This map is important because it guides the IC in allocating search resources and coordinating efforts, but it often depends almost exclusively on the missing person profile, prior experience, and subjective judgment. We propose a Bayesian model that uses publicly available terrain features data to help model lost-person behaviors. This approach enables domain experts to encode uncertainty in their prior estimations and also makes it possible to incorporate human behavior data collected in the form of posterior distributions, which are used to build a first-order Markov transition matrix for generating a temporal, posterior predictive probability distribution map. The map can work as a base to be augmented by search and rescue workers to incorporate additional information. Using a Bayesian χ ² test for goodness-of-fit, we show that the model fits a synthetic dataset well. This model also serves as a foundation for a larger framework that allows for easy expansion to incorporate additional factors such as season and weather conditions that affect the lost-person’s behaviors.     

Robotic disassembly line balancing problem: A mathematical model and ant colony optimization approach

The use of robots is significantly increasing day by day in manufacturing systems, and especially improving the efficiency of the lines. Robots can be used to complete disassembly tasks, and each of the robots can need different operation times to perform the tasks. In this paper, the balancing of the robotic disassembly line problem has been studied to develop efficient solution techniques. Firstly, a mixed-integer linear mathematical model is proposed to determine and solve the problem optimally. A case study from literature is addressed to assess and show the efficiency and effectiveness of the model to minimize cycle time. Secondly, a heuristic algorithm based on ant colony optimization is also proposed to discover a solution for especially the large-size test problems due to the complexity of the problem. The performance of the proposed heuristic algorithm is verified and compared with the different heuristic on data sets. The computational results indicate that the proposed mathematical model and the algorithms are promising for the small and large-size test problems, respectively. Finally, it should be stated that robots have great potential to use in the area of disassembly line and useful solutions provide according to test results.     

A unified framework for population-based metaheuristics

Based on the analysis of the basic schemes of a variety of population-based metaheuristics (PBMH), the main components of PBMH are described with functional relationships in this paper and a unified framework (UF) is proposed for PBMH to provide a comprehensive way of viewing PBMH and to help understand the essential philosophy of PBMH from a systematic standpoint. The relevance of the proposed UF and some typical PBMH methods is illustrated, including particle swarm optimization, differential evolution, scatter search, ant colony optimization, genetic algorithm, evolutionary programming, and evolution strategies, which can be viewed as the instances of the UF. In addition, as a platform to develop the new population-based metaheuristics, the UF is further explained to provide some designing issues for effective/efficient PBMH algorithms. Subsequently, the UF is extended, namely UFmeme to describe the Memetic Algorithms (MAs) by adding local search (memetic component) to the framework as an extra-feature. Finally, we theoretically analyze the asymptotic convergence properties of PBMH described by the UF and MAs by the UFmeme.