Performance evaluation of efficient multi-objective evolutionary algorithms for design space exploration of embedded computer systems

Multi-objective evolutionary algorithms (MOEAs) have received increasing interest in industry because they have proved to be powerful optimizers. Despite the great success achieved, however, MOEAs have also encountered many challenges in real-world applications. One of the main difficulties in applying MOEAs is the large number of fitness evaluations (objective calculations) that are often needed before an acceptable solution can be found. There are, in fact, several industrial situations in which fitness evaluations are computationally expensive and the time available is very short. In these applications efficient strategies to approximate the fitness function have to be adopted, looking for a trade-off between optimization performance and efficiency. This is the case in designing a complex embedded system, where it is necessary to define an optimal architecture in relation to certain performance indexes while respecting strict time-to-market constraints. This activity, known as design space exploration (DSE), is still a great challenge for the EDA (electronic design automation) community. One of the most important bottlenecks in the overall design flow of an embedded system is due to simulation. Simulation occurs at every phase of the design flow and is used to evaluate a system which is a candidate for implementation. In this paper we focus on system level design, proposing an extensive comparison of the state-of-the-art of MOEA approaches with an approach based on fuzzy approximation to speed up the evaluation of a candidate system configuration. The comparison is performed in a real case study: optimization of the performance and power dissipation of embedded architectures based on a Very Long Instruction Word (VLIW) microprocessor in a mobile multimedia application domain. The results of the comparison demonstrate that the fuzzy approach outperforms in terms of both performance and efficiency the state of the art in MOEA strategies applied to DSE of a parameterized embedded system.     

Black‐box position and attitude tracking for underwater vehicles by second‐order sliding‐mode technique

In this work we address the tracking control problems for autonomous underwater vehicles (AUVs). The proposed solution is based on the variable structure systems (VSS) theory and, in particular, on the second‐order sliding‐mode (2‐SM) methodology. The tuning of the controller is carried out via black‐box approach, dispensing with the knowledge of the actual AUV parameters, by simply progressively increasing a single gain parameter. The presented stability analysis includes explicitly the unmodelled actuator dynamics and the presence of external uncertain disturbances. The good performance of the proposed scheme is verified by means of simulations on a 6‐DOF AUV. Copyright © 2009 John Wiley & Sons, Ltd.     

Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²log n) time. For the parallel machine problem P|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− an O(n ³log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log ² n) time.     

Signal reconstruction in sensor networks with flat and clustered topologies

We apply signal processing techniques to the study of wireless sensor networks, whose nodes are deployed over a planar region for environmental monitoring. We address the problem of reconstructing the phenomenon of interest at a sink node, from the samples gathered by the sensors, and we evaluate the system performance in presence of both a flat and a clustered network topology. When the sensors are grouped into (possibly overlapping) clusters, the data collected within each cluster are compressed by the cluster head and sent to the sink node. By representing the compressed data through the Fourier coefficients of the field spectrum, we analyze both the case where the sensor positions are known to the sink, and the case where they are available at the cluster head only. We show that clustering significantly reduces the energy expenditure due to data transmission with respect to the case of a flat network topology, and, most importantly, we derive the possible degradation of the quality of the reconstructed field due to compression.     

A Survey of Airworthiness and Certification for UAS

The Italian SMAT project is a civilian program supported by Piemonte Region developed for the territorial monitoring and surveillance and for the prevention of natural hazards. In a different way from the previous surveillance programs, the SMAT project is based on the use of several unmanned platforms that are able to cooperate through ground coordination and control station. The flight in non-segregated airspace, needed in order to accomplish the territorial monitoring mission, is a main issue to be investigated and defined, because of the current lack of a common consensus and agreement on the regulations of UAS. The present work outlines the international initiatives that deal with the development of the regulatory framework on airworthiness and certification of UAS and their potential impact on the SMAT project.     

Social signal processing: Survey of an emerging domain

The ability to understand and manage social signals of a person we are communicating with is the core of social intelligence. Social intelligence is a facet of human intelligence that has been argued to be indispensable and perhaps the most important for success in life. This paper argues that next-generation computing needs to include the essence of social intelligence – the ability to recognize human social signals and social behaviours like turn taking, politeness, and disagreement – in order to become more effective and more efficient. Although each one of us understands the importance of social signals in everyday life situations, and in spite of recent advances in machine analysis of relevant behavioural cues like blinks, smiles, crossed arms, laughter, and similar, design and development of automated systems for social signal processing (SSP) are rather difficult. This paper surveys the past efforts in solving these problems by a computer, it summarizes the relevant findings in social psychology, and it proposes a set of recommendations for enabling the development of the next generation of socially aware computing.     

Covering a line segment with variable radius discs

The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the disc covering problem on a line. The cost of each sensor includes a fixed component f, and a variable component that is a convex function of the diameter of the field-of-view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors, the problem becomes hard. A branch-and-bound algorithm as well as an efficient heuristic are developed for the special case in which the variable cost component of each sensor is proportional to the square of the measure of the field-of-view area. The heuristic very often obtains the optimal solution as shown in extensive computational testing.     

Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners

The international planning competition (IPC) is an important driver for planning research. The general goals of the IPC include pushing the state of the art in planning technology by posing new scientific challenges, encouraging direct comparison of planning systems and techniques, developing and improving a common planning domain definition language, and designing new planning domains and problems for the research community. This paper focuses on the deterministic part of the fifth international planning competition (IPC5), presenting the language and benchmark domains that we developed for the competition, as well as a detailed experimental evaluation of the deterministic planners that entered IPC5, which helps to understand the state of the art in the field.We present an extension of pddl, called pddl3, allowing the user to express strong and soft constraints about the structure of the desired plans, as well as strong and soft problem goals. We discuss the expressive power of the new language focusing on the restricted version that was used in IPC5, for which we give some basic results about its compilability into pddl2. Moreover, we study the relative performance of the IPC5 planners in terms of solved problems, CPU time, and plan quality; we analyse their behaviour with respect to the winners of the previous competition; and we evaluate them in terms of their capability of dealing with soft goals and constraints, and of finding good quality plans in general. Overall, the results indicate significant progress in the field, but they also reveal that some important issues remain open and require further research, such as dealing with strong constraints and computing high quality plans in metric-time domains and domains involving soft goals or constraints.     

On the second-order sliding mode control of nonlinear systems with uncertain control direction

This note deals with the implementation of a second-order sliding mode control algorithm for a class of nonlinear systems in which the sign of the high-frequency gain, though constant, is unknown. A specific second-order sliding mode control algorithm, the “Suboptimal” algorithm, is properly modified in order to face the uncertainty in the control direction. It is shown that after a finite time the uncertain sign is identified and the standard finite time convergence takes place from that time on. Simulation results are provided.