Robot path planning in dynamic environments using a simulated annealing based approach

Mobile robots are widely used in many industrial fields. Research on path planning for mobile robots is one of the most important aspects in mobile robots research. Path planning for a mobile robot is to find a collision-free route, through the robot’s environment with obstacles, from a specified start location to a desired goal destination while satisfying certain optimization criteria. Most of the existing path planning methods, such as the visibility graph, the cell decomposition, and the potential field are designed with the focus on static environments, in which there are only stationary obstacles. However, in practical systems such as Marine Science Research, Robots in Mining Industry, and RoboCup games, robots usually face dynamic environments, in which both moving and stationary obstacles exist. Because of the complexity of the dynamic environments, research on path planning in the environments with dynamic obstacles is limited. Limited numbers of papers have been published in this area in comparison with hundreds of reports on path planning in stationary environments in the open literature. Recently, a genetic algorithm based approach has been introduced to plan the optimal path for a mobile robot in a dynamic environment with moving obstacles. However, with the increase of the number of the obstacles in the environment, and the changes of the moving speed and direction of the robot and obstacles, the size of the problem to be solved increases sharply. Consequently, the performance of the genetic algorithm based approach deteriorates significantly. This motivates the research of this work. This research develops and implements a simulated annealing algorithm based approach to find the optimal path for a mobile robot in a dynamic environment with moving obstacles. The simulated annealing algorithm is an optimization algorithm similar to the genetic algorithm in principle. However, our investigation and simulations have indicated that the simulated annealing algorithm based approach is simpler and easier to implement. Its performance is also shown to be superior to that of the genetic algorithm based approach in both online and offline processing times as well as in obtaining the optimal solution for path planning of the robot in the dynamic environment. The first step of many path planning methods is to search an initial feasible path for the robot. A commonly used method for searching the initial path is to randomly pick up some vertices of the obstacles in the search space. This is time consuming in both static and dynamic path planning, and has an important impact on the efficiency of the dynamic path planning. This research proposes a heuristic method to search the feasible initial path efficiently. Then, the heuristic method is incorporated into the proposed simulated annealing algorithm based approach for dynamic robot path planning. Simulation experiments have shown that with the incorporation of the heuristic method, the developed simulated annealing algorithm based approach requires much shorter processing time to get the optimal solutions in the dynamic path planning problem. Furthermore, the quality of the solution, as characterized by the length of the planned path, is also improved with the incorporated heuristic method in the simulated annealing based approach for both online and offline path planning.

Modeling and exploiting behavior patterns in dynamic environments

This paper presents a new approach to improving the effectiveness of autonomous systems that deal with dynamic environments. The basis of the approach is to find repeating patterns of behavior in the dynamic elements of the system, and then to use predictions of the repeating elements to better plan goal directed behavior. It is a layered approach involving classifying, modeling, predicting and exploiting. Classifying involves using observations to place the moving elements into previously defined classes. Modeling involves recording features of the behavior on a coarse grained grid. Exploitation is achieved by integrating predictions from the model into the behavior selection module to improve the utility of the robot's actions. This is in contrast to typical approaches that use the model to select between different strategies or plays. Three methods of adaptation to the dynamic features of the environment are explored. The effectiveness of each method is determined using statistical tests over a number of repeated experiments. The work is presented in the context of predicting opponent behavior in the highly dynamic and multi-agent robot soccer domain (RoboCup).

Multi-objective four-dimensional vehicle motion planning in large dynamic environments

This paper presents Multi-Step A* (MSA*), a search algorithm based on A* for multi-objective 4D vehicle motion planning (three spatial and one time dimension). The research is principally motivated by the need for offline and online motion planning for autonomous Unmanned Aerial Vehicles (UAVs). For UAVs operating in large, dynamic and uncertain 4D environments, the motion plan consists of a sequence of connected linear tracks (or trajectory segments). The track angle and velocity are important parameters that are often restricted by assumptions and grid geometry in conventional motion planners. Many existing planners also fail to incorporate multiple decision criteria and constraints such as wind, fuel, dynamic obstacles and the rules of the air. It is shown that MSA* finds a cost optimal solution using variable length, angle and velocity trajectory segments. These segments are approximated with a grid based cell sequence that provides an inherent tolerance to uncertainty. Computational efficiency is achieved by using variable successor operators to create a multi-resolution, memory efficient lattice sampling structure. Simulation studies on the UAV flight planning problem show that MSA* meets the time constraints of online replanning and finds paths of equivalent cost but in a quarter of the time (on average) of vector neighbourhood based A*.

Kelp detection in highly dynamic environments using texture recognition

This paper describes a texture recognition based method for segmenting kelp from images collected in highly dynamic shallow water environments by an Autonomous Underwater Vehicle (AUV). A particular challenge is image quality that is affected by uncontrolled lighting, reduced visibility, significantly varying perspective due to platform egomotion, and kelp sway from wave action. The kelp segmentation approach uses the Mahalanobis distance as a way to classify Haralick texture features from sub-regions within an image. The results illustrate the applicability of the method to classify kelp allowing construction of probability maps of kelp masses across a sequence of images.

Measuring stiffness during arm movements in various dynamic environments

The technique presented in this paper enables a simple, accurate and unbiased measurement of hand stiffness during human arm movements. Using a computer-controlled mechanical interface, the hand is shifted relative to a prediction of the undisturbed trajectory. Stiffness is then computed as the restoring force divided by the position amplitude of the perturbation. A precise prediction algorithm insures the measurement quality. We used this technique to measure stiffness in free movements and after adaptation to a linear velocity dependent force field. The subjects compensated for the external force by co-contracting muscles selectively. The stiffness geometry changed with learning and stiffness tended to increase in the direction of the external force.

Flexible self-adjustment of task deployment in dynamic environments

This paper presents an investigation into dynamic self-adjustment of task deployment and other aspects of self-management, through the embedding of multiple policies. Non-dedicated loosely-coupled computing environments, such as clusters and grids are increasingly popular platforms for parallel processing. These abundant systems are highly dynamic environments in which many sources of variability affect the run-time efficiency of tasks. The dynamism is exacerbated by the incorporation of mobile devices and wireless communication. This paper proposes an adaptive strategy for the flexible run-time deployment of tasks; to continuously maintain efficiency despite the environmental variability. The strategy centres on policy-based scheduling which is informed by contextual and environmental inputs such as variance in the round-trip communication time between a client and its workers and the effective processing performance of each worker. A self-management framework has been implemented for evaluation purposes. The framework integrates several policy-controlled, adaptive services with the application code, enabling the run-time behaviour to be adapted to contextual and environmental conditions. Using this framework, an exemplar self-managing parallel application is implemented and used to investigate the extent of the benefits of the strategy

Navigation in dynamic environments taking advantage of moving agents

Esta tese propõe uma forma diferente de navegação de robôs em ambientes dinâmicos, onde o robô tira partido do movimento de pedestres, com o objetivo de melhorar as suas capacidades de navegação. A ideia principal é que, ao invés de tratar as pessoas como obstáculos dinâmicos que devem ser evitados, elas devem ser tratadas como agentes especiais com conhecimento avançado em navegação em ambientes dinâmicos. Para se beneficiar do movimento de pedestres, este trabalho propõe que um robô os selecione e siga, de modo que possa mover-se por caminhos ótimos, desviar-se de obstáculos não detetados, melhorar a navegação em ambientes densamente populados e aumentar a sua aceitação por outros humanos. Para atingir estes objetivos, novos métodos são desenvolvidos na área da seleção de líderes, onde duas técnicas são exploradas. A primeira usa métodos de previsão de movimento, enquanto a segunda usa técnicas de aprendizagem por máquina, para avaliar a qualidade de candidatos a líder, onde o treino é feito com exemplos reais. Os métodos de seleção de líder são integrados com algoritmos de planeamento de movimento e experiências são realizadas para validar as técnicas propostas.

A multi-agent-based evolution model of innovation networks in dynamic environments

An innovation network can be considered as a complex adaptive system with evolution affected by dynamic environments. This paper establishes a multi-agent-based evolution model of innovation networks under dynamic settings through computational and logical modeling, and a multi-agent system paradigm. This evolution model is composed of several sub-models of agents' knowledge production by independent innovations in dynamic situations, knowledge learning by cooperative innovations covering agents' heterogeneities, decision-making for innovation selections, and knowledge update considering decay factors. On the basis of above-mentioned sub-models, an evolution rule for multi-agent based innovation network system is given. The proposed evolution model can be utilized to simulate and analyze different scenarios of innovation networks in various dynamic environments and support decision-making for innovation network optimization.

Situation assessment through multi-modal sensing of dynamic environments to support cognitive robot control

Awareness of emerging situations in a dynamic operational environment of a robotic assistive device is an essential capability of such a cognitive system, based on its effective and efficient assessment of the prevailing situation. This allows the system to interact with the environment in a sensible (semi)autonomous / pro-active manner without the need for frequent interventions from a supervisor. In this paper, we report a novel generic Situation Assessment Architecture for robotic systems directly assisting humans as developed in the CORBYS project. This paper presents the overall architecture for situation assessment and its application in proof-of-concept Demonstrators as developed and validated within the CORBYS project. These include a robotic human follower and a mobile gait rehabilitation robotic system. We present an overview of the structure and functionality of the Situation Assessment Architecture for robotic systems with results and observations as collected from initial validation on the two CORBYS Demonstrators.

Multi-robot hunting in dynamic environments

This paper is concerned with multi-robot hunting in dynamic environments. A BCSLA approach is proposed to allow mobile robots to capture an intelligent evader. During the process of hunting, four states including dispersion-random-search, surrounding, catch and prediction are employed. In order to ensure each robot appropriate movement in each state, a series of strategies are developed in this paper. The dispersion-search strategy enables the robots to find the evader effectively. The leader-adjusting strategy aims to improve the hunting robots’ response to environmental changes and the outflank strategy is proposed for the hunting robots to force the evader to enter a besieging circle. The catch strategy is designed for shrinking the besieging circle to catch the evader. The predict strategy allows the robots to predict the evader’s position when they lose the tracking information about the evader. A novel collision-free motion strategy is also presented in this paper, which is called the direction-optimization strategy. To test the effect of cooperative hunting, the target to be captured owns a safety-motion strategy, which helps it to escape being captured. The computer simulations support the rationality of the approach.

Modeling and exploiting behavior patterns in dynamic environments

This paper presents a new approach to improving the effectiveness of autonomous systems that deal with dynamic environments. The basis of the approach is to find repeating patterns of behavior in the dynamic elements of the system, and then to use predictions of the repeating elements to better plan goal directed behavior. It is a layered approach involving classifying, modeling, predicting and exploiting. Classifying involves using observations to place the moving elements into previously defined classes. Modeling involves recording features of the behavior on a coarse grained grid. Exploitation is achieved by integrating predictions from the model into the behavior selection module to improve the utility of the robot's actions. This is in contrast to typical approaches that use the model to select between different strategies or plays. Three methods of adaptation to the dynamic features of the environment are explored. The effectiveness of each method is determined using statistical tests over a number of repeated experiments. The work is presented in the context of predicting opponent behavior in the highly dynamic and multi-agent robot soccer domain (RoboCup)

Assessing Decision Making Skill in Complex and Dynamic Environments Using Representative and Simulated Tasks

Traditional decision making research has often focused on one's ability to choose from a set of prefixed options, ignoring the process by which decision makers generate courses of action (i.e., options) in-situ (Klein, 1993). In complex and dynamic domains, this option generation process is particularly critical to understanding how successful decisions are made (Zsambok & Klein, 1997). When generating response options for oneself to pursue (i.e., during the intervention-phase of decision making) previous research has supported quick and intuitive heuristics, such as the Take-The-First heuristic (TTF; Johnson & Raab, 2003). When generating predictive options for others in the environment (i.e., during the assessment-phase of decision making), previous research has supported the situational-model-building process described by Long Term Working Memory theory (LTWM; see Ward, Ericsson, & Williams, 2013). In the first three experiments, the claims of TTF and LTWM are tested during assessment- and intervention-phase tasks in soccer. To test what other environmental constraints may dictate the use of these cognitive mechanisms, the claims of these models are also tested in the presence and absence of time pressure. In addition to understanding the option generation process, it is important that researchers in complex and dynamic domains also develop tools that can be used by `real-world' professionals. For this reason, three more experiments were conducted to evaluate the effectiveness of a new online assessment of perceptual-cognitive skill in soccer. This test differentiated between skill groups and predicted performance on a previously established test and predicted option generation behavior. The test also outperformed domain-general cognitive tests, but not a domain-specific knowledge test when predicting skill group membership. Implications for theory and training, and future directions for the development of applied tools are discussed.

Information Exchange and Fusion in Dynamic and Heterogeneous Distributed Environments

Context awareness, dynamic reconfiguration at runtime and heterogeneity are key characteristics of future distributed systems, particularly in ubiquitous and mobile computing scenarios. The main contributions of this dissertation are theoretical as well as architectural concepts facilitating information exchange and fusion in heterogeneous and dynamic distributed environments. Our main focus is on bridging the heterogeneity issues and, at the same time, considering uncertain, imprecise and unreliable sensor information in information fusion and reasoning approaches. A domain ontology is used to establish a common vocabulary for the exchanged information. We thereby explicitly support different representations for the same kind of information and provide Inter-Representation Operations that convert between them. Special account is taken of the conversion of associated meta-data that express uncertainty and impreciseness. The Unscented Transformation, for example, is applied to propagate Gaussian normal distributions across highly non-linear Inter-Representation Operations. Uncertain sensor information is fused using the Dempster-Shafer Theory of Evidence as it allows explicit modelling of partial and complete ignorance. We also show how to incorporate the Dempster-Shafer Theory of Evidence into probabilistic reasoning schemes such as Hidden Markov Models in order to be able to consider the uncertainty of sensor information when deriving high-level information from low-level data. For all these concepts we provide architectural support as a guideline for developers of innovative information exchange and fusion infrastructures that are particularly targeted at heterogeneous dynamic environments. Two case studies serve as proof of concept. The first case study focuses on heterogeneous autonomous robots that have to spontaneously form a cooperative team in order to achieve a common goal. The second case study is concerned with an approach for user activity recognition which serves as baseline for a context-aware adaptive application. Both case studies demonstrate the viability and strengths of the proposed solution and emphasize that the Dempster-Shafer Theory of Evidence should be preferred to pure probability theory in applications involving non-linear Inter-Representation Operations.

Using the max-sum algorithm for supply chain emergence in dynamic multiunit environments

Supply chain formation (SCF) is the process of determining the set of participants and exchange relationships within a network with the goal of setting up a supply chain that meets some predefined social objective. Many proposed solutions for the SCF problem rely on centralized computation, which presents a single point of failure and can also lead to problems with scalability. Decentralized techniques that aid supply chain emergence offer a more robust and scalable approach by allowing participants to deliberate between themselves about the structure of the optimal supply chain. Current decentralized supply chain emergence mechanisms are only able to deal with simplistic scenarios in which goods are produced and traded in single units only and without taking into account production capacities or input-output ratios other than 1:1. In this paper, we demonstrate the performance of a graphical inference technique, max-sum loopy belief propagation (LBP), in a complex multiunit unit supply chain emergence scenario which models additional constraints such as production capacities and input-to-output ratios. We also provide results demonstrating the performance of LBP in dynamic environments, where the properties and composition of participants are altered as the algorithm is running. Our results suggest that max-sum LBP produces consistently strong solutions on a variety of network structures in a multiunit problem scenario, and that performance tends not to be affected by on-the-fly changes to the properties or composition of participants.

Internet-enabled international entrepreneurship : a conceptual exploration of the link between a firm’s resource base, dynamic capabilities and international market performance

It has been suggested that the accumulation of valuable resources and capabilities, such as Internet application, is not enough to support a firm’s sustainable competitive advantage, especially for high technology-mediated firms; which often operate in fast changing dynamic environments. While the idea of ‘Internet-enabled resources and capabilities’ has been recognised by RBV theorists, the notion has largely been ignored in conceptual and empirical studies. Given this finding, a conceptual framework is constructed and research issues are then developed in order to focus attention on the relationship between, the Internet and a firm’s resource base, dynamic capabilities and international market performance. We postulate that successful Internet-enabled market performance arises from those international entrepreneurial-oriented firms which encompass: international vision, international business experience, Internet-international marketing capabilities and international networking capabilities. Recommendations for future theory development are presented, along with the implications for international entrepreneurial managers in Australian small and medium sized firms