Market-based Coordination in Dynamic Environments Based on Hoplites Framework

This work focuses on multi-robot coordination based on the Hoplites framework for solving the multi-robot task allocation (MRTA) problem. Three variations of increasing complexity for the MRTA problem, spatial task allocation based on distance, spatial task allocation based on time and distance and persistent coverage have been studied in this work. The Fast Marching Method (FMM) has been used for robot path planning and providing estimates of the plans that robots bid on, in the context of the market. The use of this framework for solving the persistent coverage problem provides interesting insights by taking a high-level approach that is different from the commonly used solutions to this problem such as computing robot trajectories to keep the desired coverage level. A high fidelity simulation tool, Webots, along with the Robotic Operating System (ROS) have been utilized to provide our simulations with similar complexity to the real world tests. Results confirm that this pipeline is a very effective tool for our evaluations given that our simulations closely follow the results in reality. By modifying the replanning to prevent having costly or invalid plans by means of priority planning and turn taking, and basing the coordination on maximum plan length as opposed to time, we have been able to make improvements and adapt the Hoplites framework to our applications. The proposed approach is able to solve the spatial task allocation and persistent coverage problems in general. However, there exist some limitations. Particularly, in the case of persistent coverage, this method is suitable for applications where moderate spatial resolutions are sufficient such as patrolling.

Rigid body dynamics simulation for robot motion planning

Alan Ettlin

The development of robot motion planning algorithms is inherently a challenging task. This is more than ever true when the latest trends in motion planning are considered. Some motion planners can deal with kinematic and dynamic constraints induced by the mechanical structure of the robot. Another class of motion planners fulfill various types of optimality conditions, yet others include means of dealing with uncertainty about the robot and its environment. Sensor-based motion planners gather information typically afflicted with errors about a partially known environment in order to plan a trajectory therein. In another research area it is investigated how multiple robots best cooperate to solve a common task. In order to deal with the complexity of developing motion planning algorithms, it is proposed in this document to resort to a simulation environment. The advantages of doing so are outlined and a system named Ibex presented which is well suited to support motion planner development. The developed framework makes use of rigid body dynamics algorithms as simulation kernel. Further, various components are included which integrate the simulation into existing engineering environments. Simulation content can be conveniently developed through extensions of well-established 3D modelling tools. The co-simulation with components from other domains of physics is provided by the integration into a leading dynamic modelling environment. Robotic actuator models can be combined with a rigid body dynamics simulation using this mechanism. The same configuration also allows to conveniently develop control algorithms for a rigid body dynamics setup and offers powerful tools for handling and analysing simulation data. The developed simulation framework also offers physics-based models for simulating various sensors, most prominently a model for sensor types based on wave propagation, such as laser range finding devices. Application examples of the simulation framework are presented from the mobile robotics rough-terrain motion planning domain. Three novel rough-terrain planning algorithms are presented which are extensions of known approaches. To quantify the navigational difficulty on rough terrain, a new generic measure named "obstacleness" is proposed which forms the basis of the proposed algorithms. The first algorithm is based on Randomised Potential Field Planners (RPP) and consequently is a local algorithm. The second proposed planner extends RRTconnect , a bi-directional Rapidly Exploring Random Tree (RRT) algorithm and biases exploration of the search space towards easily traversable regions. The third planner is an extension of the second approach and uses the same heuristic to grow a series of additional local RRTs. This allows it to plan trajectories through complex distributions of navigational difficulty benefitting from easy regions throughout the motion plan. A complete example is shown in which the proposed algorithms form the basis for sensor-based dynamic re-planning simulated in the presented framework. In the scenario, a simulated planetary rover navigates a long distance over rough terrain while gathering sensor data about the terrain topography. Where obstacles are sensed which interfere with the original motion plan, dynamic re-planning routines are applied to circumnavigate the hindrances. In the course of this document a complete simulation environment is presented by means of a theoretical background and application examples which can significantly support the development of robot motion planning algorithms. The framework is capable of simulating setups which fulfil the requirements posed by stateof-the-art motion planning algorithm development.

EPFL2006

Object-oriented approach for dynamic system modelling and simulation

Adel Besrour

Software engineering always cares to provide solutions for building applications as close as possible to what they should be, according to the requirements and the final users needs. Systems behavior simulation is a very common application to virtually reproduce and often predict the real-world behavior. Simulation is one of the most operational research tool in a large variety of engineering and scientific domains: Transport, telecommunication, medicine, chemical processes, physics, etc. The complexity of such application is relative to the increasing complexity of the systems. In this context, it is relevant to bring together different tools and formalisms such as markovian chain, Petri nets, etc., to improve the existent approaches and so to answer the simulations performances needs. The principle objective of this thesis is to bring together techniques from software engineering and safety engineering in order to improve the state of the art of modeling and simulation of dynamic systems in the industrial context. In addressing this objective, this work initially involves defining the essential limitations of the used formalisms, methods and tools regarding from one hand the software engineering modeling and simulation techniques and from the other hand the existent risk analysis methodologies. This work is conducted with respect to the problem of danger identification, considering the context of the complex systems behavior and their interaction with the human operator. In software engineering, it is well known that Petri/high-level nets have attractive characteristics to be used in systems simulation and behavior prediction such as the natural graphical representation, and their well-defined semantic. They are well-suited for the description of complex situations with concurrency (interleaving and true concurrency depending on the underlying semantics), conflict and confusion. However, the absence of structuring capabilities has been one of the main criticisms raised against Petri nets/high-level nets. Thus, there have been many attempts to introduce structuring principles in nets of this kind [BCM88] [Kie89] [JR91]. The attractive characteristics of Petri/high-level nets have prompted researchers to enrich these formalisms with object-oriented features. CO-OPN (Concurrent Object-Oriented Petri Net) approach, brings together the power of both Petri/high-level nets and object-orientation techniques, it has been devised so as to offer an adequate framework for the specification and design of large scale concurrent system [BG91]. CO-OPN, as a powerful modeling tool, has been used in a limited way to simulate systems. This work aims to provide a CO-OPN extension to allow a more realistic systems' simulation. Actually, its simulator semantic uses to be a suitable approach for modeling near closed systems and software components, because they need to loose coupling with external world. But, when we model more realistic problems like industrial processes, where human interaction is a relevant event, this approach is not sufficient to catch all system activity attributes. Moreover, the CO-OPN interpretation process does not allow interaction with the object internal states. This work provides a new solution to overcome CO-OPN simulation limitations and a set of prototypes to assist dynamic systems simulations. Furthermore, this work has been conducted in a Risk Analysis (RA) context, a domain where computer-based simulations research are of utmost interest. Actually, classical approaches used to address complex workplace hazard in a limited way, using checklists or sequence models. Moreover, the use of single oriented methods, such as AEA (man-oriented), FMEA (machine oriented) or HAZOP (process oriented), is not satisfactory to overcome the increasing sophistication of industrial processes. The automation of a part of the analysis process as well as the multiple-oriented approach allowed by dynamic modeling may indeed enhance significantly the analysis completeness and reduce the time analyzing time. This work, based on Object Oriented Petri net formalism (CO-OPN), propose an alternative multi-oriented approach where existent methods limitations have been criticized to develop a dynamic model, MORM (Man-machine Occupational Risk Modeling). A real industrial system (metal wire making process) has been specified to implement the different approach steps (system identification, model application, system simulation, system analysis).

EPFL2005

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 GHz separated in a 9-cores architecture. This exponential evolution following the famous "Moore's Law" is possible thanks to the innovations made in every domain implied in a chip conception and allows chipset creation targeting a more and more wide range of applications. This variety of processors implies a great number of variations in the hardware choices, to match application (general purpose processor, digital signal processor, application-specific processor…), performance requirements and / or other operative constraints such as power consumptions. The applications running on these powerful solutions are growing in complexity exponentially as well, relying on more and more sophisticated software. Consequently the design team is facing a real challenge when designing and implementing an optimal architectural solution. To ease their task, the trend in computer aided design is to develop integrated frameworks for simulation and design, providing all the tools needed during the process, in a top-down approach. These tools allow system specification by means of abstract concurrent entities down to final implementation by means of successive refinements of the different entities and of the communication among then. In parallel, these hardware solutions run applications of a constantly increasing complexity, leading to the need for more and more intensive specification and validation tasks, by means of abstract software descriptions, typically referred to as verification models. These models implement all the functionalities of the application and thus, from the end of this specification phase, the abstract description of the application in the verification model becomes the most reliable reference for the corresponding application. All these reasons make the intuitive understanding of the processing complexity and tend to create redesign loops in the conception process when realizing that the initial architecture choices were sub-optimal (or even wrong), preventing the system to meet the desired performance constraints. In this case, a costly re-design iteration is mandatory, targeting a new platform choice but introducing delay and cost in the design causing the project to arrive too late on the market. Obviously, to eliminate these re-design iterations and to be able to help as soon as possible, the preliminary complexity analysis should be performed before starting the design of the target architecture. Since the first step of the design cycle implies an algorithm description through a verification model, it is desirable to perform the complexity study on this model. Indeed, though considerable efforts are carried out on developing powerful co-design tools, by means high-level abstract descriptions, fast prototyping and flexible design-reusability; no automatic tool is available to help the designer in the first analysis and comprehension phase. Moreover, the size of verification models is growing together with the complexity of the applications, and it is not surprising to have to deal with verification models of tens of thousands of source code lines; consequently, paper-and-pencil and manual-instrumentation analysis methods are neither feasible nor reliable any longer. Furthermore, static complexity evaluations, not taking into account the dynamic dependency of the complexity from the input data, are becoming less and less meaningful for the development of cost-effective solutions. Worst-case analysis is typically suitable for real-time control applications but it cannot be applied in all the cases in which quality-of-service/cost trade-offs are of concern; for instance, a multimedia or signal-processing architecture developed to support the worst-case scenario would simply result to be too expensive and under-exploited for most of the processing time. This dissertation presents a new approach to algorithmic complexity analysis, called the Software Instrumentation Tool (SIT), based on the previous observations and aiming at filling the gap in state of the art tools. The main goal of the SIT is to provide a high-level analysis framework for both a faithful design-oriented evaluation of the computational complexity of verification models and a hardware simulation of the projected architecture. The breakthrough in this version of the SIT is to provide a full set of results about complexity in a complete framework, allowing to use all these data in a methodology able to fill the gap from verification model to hardware implementation or algorithm porting. The analysis is performed at the highest possible abstraction level, i.e. at source code language level, in order to adhere to the same degree of abstraction of verification models; that is, the analysis is not biased by the underlying architecture over which the verification model is tested or by the compilation process. The analysis strictly depends on the input data, in order to take into account the real algorithmic complexity in real working conditions and relies on a completely automatic process, performed directly on the source code of verification models, without forcing the designer to make any manual modification such as source code rewriting or manual instrumentation. SIT approach to complexity analysis is based on the instrumentation by means of C++ operator overloading. SIT analyzes C source code and is capable to instrument, automatically, any legal C data-type or operation or statement, providing eventually an exhaustive complexity analysis at C language level. The tool is building on a core system (a core for the base algorithmic complexity, a second for memory analysis) and supports module extensions (a module for critical path evaluation, a module for data transfer, both can be plugged in the memory core). All the cores and modules are reporting their results in a single visual interface, allowing a quick and efficient complexity overview as well as an in-depth result exploration. As SIT allows extracting meaningful complexity measures directly from the verification models in the preliminary analysis and comprehension phase, the designer benefits from a tool-assisted approach allowing to step to the latest design phases through intermediate tools. The results provided by the first version of the SIT are computational data (what types of operation are performed? On which type of data? ...) and memory usage analysis (how many memory accesses? In which function?). This build of the SIT includes a customizable memory usage analysis, made possible by the simulation of (customizable) virtual memory architectures; this allows to focus the analysis on other aspects of the algorithmic complexity which could not otherwise be estimated by means of static analysis methods, or software profilers, or instruction-level profilers. Another novelty in the SIT is the data-transfer module, allowing both a quick and efficient overview of the main data flows inside the virtual architecture (thanks to a graphical representation of the mains transfers) and a precise in depth analysis of bandwidth and data transfers between functions (thanks to the detailed view included in Sitview). The latest result is the critical path evaluation analysis, allowing to detect the major functions of the execution tree and to extract information about parallelism at different level, from function to algorithm level. All these information are provided through the SIT graphical interface SitView, and a methodology is described to step from the high-level verification model in C to an actor language partioning based on the tool analysis. This partition can be used with dedicated actor languages to create a FPGA code or to create an optimized hardware solution, most probably better than an instinctively created hardware.

EPFL2007