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.     

Learning natural scene categories by selective multi-scale feature extraction

Natural scene categorization from images represents a very useful task for automatic image analysis systems. In the literature, several methods have been proposed facing this issue with excellent results. Typically, features of several types are clustered so as to generate a vocabulary able to describe in a multi-faceted way the considered image collection. This vocabulary is formed by a discrete set of visual codewords whose co-occurrence and/or composition allows to classify the scene category. A common drawback of these methods is that features are usually extracted from the whole image, actually disregarding whether they derive properly from the natural scene to be classified or from foreground objects, possibly present in it, which are not peculiar for the scene. As quoted by perceptual studies, objects present in an image are not useful to natural scene categorization, indeed bringing an important source of clutter, in dependence of their size.     

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.