QoS metrics-in-the-loop for endowing runtime self-adaptation to robotic software architectures

Multimedia Tools and Applications - The design of robots capable of operating autonomously in changing and unstructured environments, requires using complex software architectures in which,...     

Application-dependent dynamic monitoring of distributed andparallel systems

Achieving high performance for parallel or distributed programs often requires substantial amounts of information about the programs themselves, about the systems on which they are executing, and about specific program runs. The monitoring system that collects, analyzes, and makes application-dependent monitoring information available to the programmer and to the executing program is presented. The system may be used for off-line program analysis, for on-line debugging, and for making on-line, dynamic changes to parallel or distributed programs to enhance their performance. The authors use a high-level, uniform data model for the representation of program information and monitoring data. They show how this model may be used for the specification of program views and attributes for monitoring, and demonstrate how such specifications can be translated into efficient, program-specific monitoring code that uses alternative mechanisms for the distributed analysis and collection to be performed for the specified views. The model's utility has been demonstrated on a wide variety of parallel machines     

An MO‐GVNS algorithm for solving a multiobjective hybrid flow shop scheduling problem

This paper addresses the multiobjective hybrid flow shop (MOHFS) scheduling problem. In the MOHFS problem considered here, we have a set of jobs that must be performed in a set of stages. At each stage, we have a set of unrelated parallel machines. Some jobs may skip stages. The evaluation criteria are the minimizations of makespan, the weighted sum of the tardiness, and the weighted sum of the earliness. For solving it, an algorithm based on the multiobjective general variable neighborhood search (MO‐GVNS) metaheuristic, named adapted MO‐GVNS, is proposed. This work also presents and compares the results obtained by the adapted MO‐GVNS with those of four other algorithms: multiobjective reduced variable neighborhood search, nondominated sorting genetic algorithm II (NSGA‐II), and NSGA‐III, and another MO‐GVNS from the literature. The results were evaluated based on the Hypervolume, Epsilon, and Spacing metrics, and statistically validated by the Levene test and confidence interval charts. The results showed the efficiency of the proposed algorithm for solving the MOHFS problem.     

A variable neighborhood search for flying sidekick traveling salesman problem

The efficiency and dynamism of unmanned aerial vehicles, or drones, have presented substantial application opportunities in several industries in the last years. Notably, logistic companies have given close attention to these vehicles to reduce delivery time and operational cost. A variant of the traveling salesman problem (TSP), called the flying sidekick traveling salesman problem, was introduced involving drone‐assisted parcel delivery. The drone launches from the truck, proceeds to deliver parcels to a customer, and then is recovered by the truck at a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic where the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the general variable neighborhood search is employed to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve significantly delivery time. Furthermore, we provide a new set of instances based on the well‐known traveling salesman problem library instances.     

Towards a smooth design process for static communicative node‐link diagrams

Node‐link infographics are visually very rich and can communicate messages effectively, but can be very difficult to create, often involving a painstaking and artisanal process. In this paper we present an investigation of node‐link visualizations for communication and how to better support their creation. We begin by breaking down these images into their basic elements and analyzing how they are created. We then present a set of techniques aimed at improving the creation workflow by bringing more flexibility and power to users, letting them manipulate all aspects of a node‐link diagram (layout, visual attributes, etc.) while taking into account the context in which it will appear. These techniques were implemented in a proof‐of‐concept prototype called GraphCoiffure, which was designed as an intermediary step between graph drawing/editing software and image authoring applications. We describe how GraphCoiffure improves the workflow and illustrate its benefits through practical examples.     

Distributed shared abstractions (DSA) on multiprocessors

Any parallel program has abstractions that are shared by the program's multiple processes. Such shared abstractions can considerably affect the performance of parallel programs, on both distributed and shared memory multiprocessors. As a result, their implementation must be efficient, and such efficiency should be achieved without unduly compromising program portability and maintainability. The primary contribution of the DSA library is its representation of shared abstractions as objects that may be internally distributed across different nodes of a parallel machine. Such distributed shared abstractions (DSA) are encapsulated so that their implementations are easily changed while maintaining program portability across parallel architectures. The principal results presented are: a demonstration that the fragmentation of object state across different nodes of a multiprocessor machine can significantly improve program performance; and that such object fragmentation can be achieved without compromising portability by changing object interfaces. These results are demonstrated using implementations of the DSA library on several medium scale multiprocessors, including the BBN Butterfly, Kendall Square Research, and SGI shared memory multiprocessors. The DSA library's evaluation uses synthetic workloads and a parallel implementation of a branch and bound algorithm for solving the traveling salesperson problem (TSP)     

On graph reasoning

In this paper, we study the (positive) graph relational calculus. The basis for this calculus was introduced by Curtis and Lowe in 1996 and some variants, motivated by their applications to semantics of programs and foundations of mathematics, appear scattered in the literature. No proper treatment of these ideas as a logical system seems to have been presented. Here, we give a formal presentation of the system, with precise formulation of syntax, semantics, and derivation rules. We show that the set of rules is sound and complete for the valid inclusions, and prove a finite model result as well as decidability. We also prove that the graph relational language has the same expressive power as a first-order positive fragment (both languages define the same binary relations), so our calculus may be regarded as a notational variant of the positive existential first-order logic of binary relations. The graph calculus, however, has a playful aspect, with rules easy to grasp and use. This opens a wide range of applications which we illustrate by applying our calculus to the positive relational calculus (whose set of valid inclusions is not finitely axiomatizable), obtaining an algorithm for deciding the valid inclusions and equalities of the latter.