This paper studies the Dynamic Electric Dial-A-Ride Problem (DEDARP), which is a combinatorial optimisation problem that has applications in real-world ridesharing services with electric vehicles. In addition to the challenges from classical scheduling and route planning, we consider here the extra challenge of making real-time dispatching decisions in dynamic environments with new requests arriving over time and selecting proper times for the vehicles to recharge. To solve DEDARP effectively, we propose a Genetic Programming Hyper-Heuristic (GPHH) that evolves heuristics/policies to dispatch vehicles in real time. We have developed a simulation process that generates a solution for any given instance by two policies, one for vehicle allocation and the other for request allocation, and design fitness evaluations based on the simulation. Moreover, we propose a multi-tree GP to evolve these two policies simultaneously, which makes use of advanced terminals to comprehensively represent the state. Experimental results on a wide range of instances show that GPHH can evolve effective policies that make significantly better real-time dispatching decisions than human-designed policies based on prior knowledge.

A common aim in real-world optimisation problems is to seek a solution offering highest performance on expected scenarios, but at the same time guaranteeing an at least acceptable performance on worst-case scenarios. Competitive coevolution evolves a population of solutions alongside a population of difficult scenarios in order to find so-called robust solutions. However, solutions with maximal worst-case performance often exhibit poor performance on more typical scenarios. Existing coevolutionary approaches generally favour such solutions over ones which sacrifice only a small amount of average performance for an almost as large gain in worst-case performance, despite the latter being favourable in most practical applications. We present a new coevolutionary algorithm which treats average performance and worst-case performance as two objectives of a bicriteria optimisation problem and seeks the corresponding Pareto front. Such an algorithm enables the discovery of solutions with strong performance in both of these metrics, which would otherwise be rejected if optimising for only one. Our algorithm constitutes the first coevolutionary approach to this solution concept. We also provide experimental results on the performance of this algorithm on the design of smart controllers for the management of energy flow between buildings, renewable energy sources, and electric vehicles.

Automated machine learning (AutoML) has emerged as a pivotal tool for applying machine learning (ML) models to real-world problems. Tree-based pipeline optimization tool (TPOT) is an AutoML framework known for effectively solving complex tasks. TPOT's search involves two fundamental objectives: finding optimal pipeline structures (i.e., combinations of ML operators) and identifying suitable hyperparameters for these structures. While its use of genetic programming enables TPOT to excel in structural search, its hyperparameter search, involving discretization and random selection from extensive potential value ranges, can be computationally inefficient. This paper presents a novel methodology that heavily restricts the initial hyperparameter search space, directing TPOT's focus towards structural exploration. As the search evolves, Bayesian optimization (BO) is used to refine the hyperparameter space based on data from previous pipeline evaluations. This method leads to a more targeted search, crucial in situations with limited computational resources. Two variants of this approach are proposed and compared with standard TPOT across six datasets, with up to 20 features and 20,000 samples. The results show the proposed method is competitive with canonical TPOT, and outperforms it in some cases. The study also provides new insights into the dynamics of pipeline structure and hyperparameter search within TPOT.

Tree-based pipeline optimization tool (TPOT) is used to automatically construct and optimize machine learning pipelines for classification or regression tasks. The pipelines are represented as trees comprising multiple data transformation and machine learning operators --- each using discrete hyper-parameter spaces --- and optimized with genetic programming. During the evolution process, TPOT evaluates numerous pipelines which can be challenging when computing budget is limited. In this study, we integrate TPOT with Bayesian Optimization (BO) to extend its ability to search across continuous hyper-parameter spaces, and attempt to improve its performance when there is a limited computational budget. Multiple hybrid variants are proposed and systematically evaluated, including (a) sequential/periodic use of BO and (b) use of discrete/continuous search spaces for BO. The performance of these variants is assessed using 6 data sets with up to 20 features and 20,000 samples. Furthermore, an adaptive variant was designed where the choice of whether to apply TPOT or BO is made automatically in each generation. While the variants did not produce results that are significantly better than "standard" TPOT, the study uncovered important insights into the behavior and limitations of TPOT itself which is valuable in designing improved variants.

It is highly desirable to adapt the reference vectors to unknown Pareto fronts (PFs) in decomposition-based evolutionary many-objective optimization. While adapting the reference vectors enhances the diversity of the achieved solutions, it often decelerates the convergence performance. To address this dilemma, we propose to adapt the reference vectors and the scalarizing functions in a coordinated way. On the one hand, the adaptation of the reference vectors is based on a local angle threshold, making the adaptation better tuned to the distribution of the solutions. On the other hand, the weights of the scalarizing functions are adjusted according to the local angle thresholds and the reference vectors’ age, which is calculated by counting the number of generations in which one reference vector has at least one solution assigned to it. Such coordinated adaptation enables the algorithm to achieve a better balance between diversity and convergence, regardless of the shape of the PFs. Experimental studies on MaF, DTLZ, and DPF test suites demonstrate the effectiveness of the proposed algorithm in solving problems with both regular and irregular PFs.

Most reference vector-based decomposition algorithms for solving multiobjective optimization problems may not be well suited for solving problems with irregular Pareto fronts (PFs) because the distribution of predefined reference vectors may not match well with the distribution of the Pareto-optimal solutions. Thus, the adaptation of the reference vectors is an intuitive way for decomposition-based algorithms to deal with irregular PFs. However, most existing methods frequently change the reference vectors based on the activeness of the reference vectors within specific generations, slowing down the convergence of the search process. To address this issue, we propose a new method to learn the distribution of the reference vectors using the growing neural gas (GNG) network to achieve automatic yet stable adaptation. To this end, an improved GNG is designed for learning the topology of the PFs with the solutions generated during a period of the search process as the training data. We use the individuals in the current population as well as those in previous generations to train the GNG to strike a balance between exploration and exploitation. Comparative studies conducted on popular benchmark problems and a real-world hybrid vehicle controller design problem with complex and irregular PFs show that the proposed method is very competitive.

Acquisition functions for surrogate-assisted many-objective optimization require a delicate balance between convergence and diversity. However, the conflicting nature between many objectives may lead to an imbalance between exploration and exploitation, resulting in a low efficiency in search for a set of optimal solutions that can well balance convergence and diversity. To meet this challenge, we propose an adaptive model management strategy assisted by two sets of reference vectors, one set of adaptive reference vectors accounting for convergence while the other set of fixed reference vectors for diversity. Specifically, we first propose a new acquisition function that calculates an amplified upper confidence bound (AUCB). Two optimization processes are performed in parallel to optimize the acquisition function, each based on one of the two sets of reference vectors. Then, we select one promising candidate solution according to diversity or convergence from the nondominated solutions obtained by the two optimization processes. The experimental results on four suites of test functions as well as six real-world application problems demonstrate the competitive performance of the proposed reference vector-assisted adaptive model management strategy, in comparison with seven state-of-the-art surrogate-assisted evolutionary algorithms (SAEAs).

In practical multi/many-objective optimization problems, a decision maker is often only interested in a handful of solutions of interest (SOI) instead of the entire Pareto Front (PF). It is therefore of significant research interest to design algorithms that can automatically detect SOIs and search around them instead of attempting to find the entire PF. However, this is challenging for a number of reasons. First and foremost, the interpretation of the underlying measures in terms of quantifying trade-off information for SOIs is not straightforward. Scalability is also an issue for most of such existing measures. Additionally, for many-objective algorithms that rely on decomposition, adaptation of reference directions and appropriate means to scale the objectives to maintain solution density around SOIs is not trivial. Lastly, constraints and decision-space are often overlooked in the existing studies but are important for practical applications. In this work, we present a simple approach to identify SOIs, using normalized net gain over nadir point and angle of influence. We illustrate the utility of the measure for offline and online identification of SOIs using a range of unconstrained and constrained benchmarks and practical design problems spanning up to 5 objectives. We also show further analysis in decision-space for an application problem to aid decision-making in practical scenarios.

For problems with irregular Pareto fronts, only part of the objective space is covered by optimal solutions. Most decomposition based evolutionary many-objective algorithms, however, predefine uniformly distributed weight or reference vectors, making them less suited for problems with irregular Pareto fronts, since many weight or reference vectors will be wasted. To address the above issue, this paper proposes a variant of the reference vector guided evolutionary algorithm by adjusting reference vectors according to the distribution of the solutions in the current population to make sure that most reference vectors are associated with solutions. A secondary selection criterion based on the dominance relationship is adopted in addition to the angle penalized distance based selection so that a sufficient number of solutions can survive and be passed to the next generation. Experiments on 12 irregular test problems with 60 instances show that the proposed algorithm is competitive compared to the state-of-the-art algorithms for solving problems with irregular Pareto fronts.

In industry we see an increasing interest in (evolutionary) many objective optimization algorithms. However, the majority of engineers only using, not researching, optimizers have a limited understanding of the pros and cons of different algorithms and therefore rely on either third-party recommendations or benchmark tests to pick the most suitable methods for their problems. Unfortunately, most benchmarks are targeting an academic audience leaving the practitioner often in doubt about the correct choices. In this article we try to outline the essential requirements for a many-objective optimization algorithm portfolio management from an industrial perspective and compare the situation in our field to another domain with similar issues, image processing. We want to address one of the core practical issues: “Given a limited computational or time budget for my optimization project, which optimization algorithms should I try?”.

For a commercial building or campus, the management of local energy production, storage, and consumption, promises substantial gains in efficiency and reduced costs and emissions. When facility managers are planning updates to an existing building complex, they face a variety of options for investment. This work targets to provide support for this investment decision by performing a many-objective optimization (MAO) of the system configuration considering initial investment cost, running costs, CO2emissions, and system resilience. In our specific example the potential investment covers a photo voltaic (PV) system, a stationary battery, and a heat storage. We also consider potential changes to the operation of an existing co-generator for heat and power (CHP), by optimizing controller parameters. The proposed system is simulated using a Modelica-based software environment. In this work we show the results of our configuration optimization using the well-known NSGA-III algorithm and also consider the problem of variable run-times of the simulator on the optimization process especially for a parallel execution of fitness evaluations on a computing cluster.

In the fields of multi- and many-objective optimization methods, the hypervolume of a set of solutions is a very useful measure for assessing the current state of the optimization process. It is also the fundamental quality criterion for the well-known SMS-EMOA (S-metric selection evolutionary multi-objective optimization), which is one of the best many objective optimization algorithms known at the moment. Unfortunately, the computation of the hypervolume for a given set of solutions is a time-consuming effort which scales unfavorably with the number of objectives and the size of the population. In this work we analyzed a number of algorithms for hypervolume computation and systematically measured their computational effort for different numbers of objectives and population size. We compared three established standard algorithms that are used in the Shark optimization library and a recent approach by While et al. We also included an approximation computation algorithm proposed by Ishibuchi et al., where we additionally evaluated the precision of the approximation computation and its impact on the selection process within an optimization run. Our findings indicate that the algorithm by While et al. outperforms the three other exact algorithms for a wide range of settings. The Ishibuchi algorithm was shown to have a slightly negative effect on the selection process, but for very large population sizes or number of objectives, the approximation method might be the only viable alternative.

This paper presents a system that uses various simple auditory and visual features to achieve human-robot dialog scene analysis. Our scene analysis system is able to learn how many speakers are in the scenario, where the speakers are and who is currently speaking. Speakers are unknown in advance. A visual short-term-memory (STM) helps to memorize persons, even if they disappear from the camera's field of view for a while due to movements of persons or the robot head. In comparison to our previous work, we apply more visual features such as height, color and texture features of different upper body parts, to improve the scene representation performance. We show that our system is able to assign words to corresponding speakers. A speaker is recognized again when he leaves and enters the scene, or changes his position even with a newly appearing person.

While a robot is moving, ego noise is generated due to the fans and motors of the robot. Furthermore, a robot is not only subject to the ego noise, but also to the ambient noise of the environment, both having different short-term signal characteristics. Because ego-motion noise generated by the motors is non-stationary, and the BackGround Noise (BGN) is stationary, one single noise estimation method is unable to track the changes in both noise spectra rapidly and accurately. Therefore, we propose to use the combination of two different noise estimation methods adequate for each one of co-existing noise types in a unified framework: 1) a stationary noise estimation method called Histogram-based Recursive Level Estimation (HRLE) and 2) a non-stationary noise estimation method called Template-based Estimation (TE). In this paper, we evaluate the performance of several single-channel based noise estimation techniques in terms of their prediction accuracy and quality of the speech signals enhanced by spectral subtraction methods. The experimental results show that our system, compared to the conventional single-stage noise estimation methods, achieves better performance in attaining signal quality and improving word correct rates.

Using pre-recorded templates to estimate and suppress the ego noise of a robot is advantageous because this method is able to cope with the non-stationarity of this particular type of noise. However, standard template-based estimation requires human intervention in the offline training sessions, storage of large amounts of data and does not adapt to the dynamical changes in the environmental conditions. In this paper we investigate the feasibility of an incremental template learning system to tackle these drawbacks. Incremental learning enables the system to acquire new templates on the fly and update the older ones appropriately. Whilst allowing the system to continually increase its knowledge and enhancing its estimation performance, this learning scheme also reduces the size of the database. We evaluate the performance of the proposed noise estimation method in terms of its estimation accuracy, quality of speech signals enhanced by spectral subtraction method, and size of database. The experimental results show that our system compared to conventional single-channel noise estimation methods achieves better performance in attaining signal quality and improving word correct rates.

Domestic tasks such as grasping or navigation for robotic systems can be supported by vision. However, the environment provides a vast amount of visual information and concentrating on the information related to the task being undertaken is an important job. Active vision is an approach that provides such a filtering mechanism by using camera movements to bring relevant information into the focus of attention. However timing of gaze shifts (i.e. when to look where) is crucial for cognitive tasks to proceed simultaneously (multitasking). We developed a framework that learns task dependent management of gaze control. We adopted a systems approach where individual visual processes were formalised as modules such as a colour saliency module or object recognition module. Modules may generate motor commands for gaze shifts to acquire visual information relevant to their operation. The system learns how to use its modules (i.e. when to give motor control access to which module) for a task in a reward-based concept. The framework was used in a reaching-while-interacting scenario using the humanoid iCub in a simulation environment.

Noise generated due to the motion of a robot is not desired, because it deteriorates the quality and intelligibility of the sounds recorded by robot-embedded microphones. It must be reduced or cancelled to achieve automatic speech recognition with a high performance. In this work, we divide ego-motion noise problem into three subdomains of arm, leg and head motion noise, depending on their complexity and intensity levels. We investigate methods that make use of single-channel and multi-channel processing in order to suppress ego noise separately. For this purpose, a framework consisting of a microphone-array-based geometric source separation, a consequent post filtering process and a parallel module for template subtraction is used. Furthermore, a control mechanism is proposed, which is based on signal-to-noise ratio and instantaneously detected motions, to switch to the most suitable method to deal with the current type of noise. We evaluate the proposed techniques on a humanoid robot using automatic speech recognition (ASR). The preliminary results of isolated word recognition show the effectiveness of our methods by increasing the word correct rates up to 50% compared to the single channel recognition in arm and leg motion noises and up to 25% in very strong head motion noises.

This paper presents a system that gives a mobile robot the ability to recognize target speaker's speech, even if the robot performs an action and there are multiple speakers talking in the room. Associated problems to this system are twofold: (1) While the robot is moving, the joints inevitably generate ego-motion noise due to its motors. (2) Recognizing target speech against other interfering speech signals is a difficult task. Since typical solutions to (1) and (2), motor noise suppression and sound source separation, both introduce distortion to the processed signals, the performance of automatic speech recognition (ASR) deteriorates. Instead of removing the ego-motion noise with conventional noise suppression methods, in this work, we investigate methods to eliminate the unreliable parts of the audio features that are contaminated by the ego-motion noise. For this purpose, we model masks that filter unreliable speech features based on the ratio of speech and motor noise energies. We analyze the performance of the proposed technique under various test conditions by comparing it to the performance of existing Missing Feature Theory-based ASR implementations. Finally, we propose an integration framework for two different masks that are designed to eliminate ego noise and to filter the leakage energy of interfering sound sources. We demonstrate that the proposed methods achieve a high ASR accuracy.

Interactions between humans or humanoids and their environment through tasks like grasping or manipulation typically require accurate depth information. The human vision system integrates various monocular and binocular depth estimation mechanisms in order to achieve robust and reliable depth perception. Such an integrated approach can be applied to humanoid depth perception. Integration requires a knowledge of the characteristics of the methods being combined. Three different methods incorporating active vision (stereo disparity, vergence and familiar size) were statistically examined and combinations of these methods based on this statistical examination were investigated. We found evidence that active vision provides better depth estimations than the standard static-parallel stereo methods examined within interaction range and therefore is better suited for tasks like reaching, grasping and manipulation. We also demonstrate that a combination of methods have the potential to increase the accuracy of estimations.

The position of a sound source is an important information for robotic systems to be extracted from a sound. Of the three spherical coordinates (azimuth, elevation, distance) only the azimuth direction is extracted in most robot audition systems. So far rarely investigated is the issue of estimating the distance between robot and sound source. In this article we describe a study on distance estimation using a binaural robot system in an indoor environment for sounds ranging in distance from 0.5 to 6m. We investigated several proposed audio cues like interaural differences (IID and ITD), sound amplitude, and spectral characteristics. All cues are computed within the framework of audio proto objects. In an extensive experimental setup with more than 10000 sounds we found that both mean signal amplitude and binaural cues can, under certain circumstances, provide a very reliable distance estimation. There was no observable effect of frequency dependent attenuation so that the spectral amplitude cue was only slightly above chance level. We also investigated the loss of precision of azimuth estimation with distance. In contrast to what could be expected, the performance does not severely deteriorate when the system is calibrated for different distances.

While a robot is moving, the joints inevitably generate noise due to its motors, i.e. ego-motion noise. This problem is very crucial, especially in humanoid robots, because it tends to have a lot of joints and the motors are located closer to the microphones than the sound sources. In this work, we investigate methods for the prediction and suppression of the ego-motion noise. In the first part, we analyze the performance of different noise subtraction strategies, assuming that the noise prediction problem has been solved. In the second part, we present some results for a noise prediction scheme based on the current robot joint status. Performance is evaluated for a number of criteria, including Automatic Speech Recognition (ASR). We demonstrate that our method improves recognition performance during ego-motion considerably.

In this article we present a new framework for auditory processing that combines feature extraction and grouping processes to form what we call audio proto objects. These proto objects combine an arbitrary number of audio features in a compact representation that allows a more precise sound localization and also better interfacing to behavior-control in robotics. We compare our standard sound localization system with the new approach in several scenarios to demonstrate the potential of the new approach.

Based on inspirations from infant development we present a system which learns associations between acoustic labels and visual representations in interaction with its tutor. The system is integrated with a humanoid robot. Except for a few trigger phrases to start learning all acoustical representations are learned online and in interaction. Similar, for the visual domain the clusters are not predefined and fully learned online. In contrast to other interactive systems the interaction with the acoustic environment is solely based on the two microphones mounted on the robots head. In this paper we give an overview on all key elements of the system and focus on the challenges arising from the headset-free learning of speech labels. In particular we present a mechanism for auditory attention integrating bottom-up and top-down information for the segmentation of the acoustic stream. The performance of the system is evaluated based on offline tests of individual parts of the system and an analysis of the online behavior.

We present a system for online extraction of the fundamental frequency and the first four formant frequencies from a speech signal. In order to evaluate the performance of the extraction a resynthesis of the speech signal is performed. The resynthesis is based on the extracted frequencies and the energy of the input signal at the formant locations. The extraction of the fundamental frequency and the formants is robust against room echoes and interfering noise. In order to improve the robustness against background noise a noise reduction was implemented. Tests in three rooms of different size at varying distances to the system (up to 8 m yielding an SNR of approx. 0 dB) were performed.

It is a common assumption that with just two microphones only the azimuth angle of a sound source can be estimated and that a third, orthogonal microphone (or set of microphones) is necessary to estimate the elevation of the source. Recently, using specially designed ears and analyzing spectral cues several researchers managed to estimate sound source elevation with a binaural system. In this work, we show that with two bionic ears both azimuth and elevation angle can be determined using both binaural (e.g. IID and ITD) and spectral cues. This ability can also be used to disambiguate signals coming from the front or back. We present a detailed analysis of both azimuth and elevation localization performance for binaural and spectral cues in comparison. We demonstrate that with a small extension of a standard binaural system a basic elevation estimation capacity can be gained.

We present a system for an online-adaptation of auditory-motor maps that doesn't require a special set-up or dedicated robot movements and can therefore work during the normal operation of the robot. Our approach is based purely on auditory cues and motor position feedback for estimating the correct sound source position. The system can learn the correct auditory-motor map within 1-2 hours, starting from a random initialization, in a room with an active radio as the main sound source.

We present a new way of modelling the Precedence Effect to enable the robust measurement of localization cues (ITD and IID) in echoic environments. Based on this we developed a localization system which is inspired by the auditory system of mammals. It uses a Gammatone filter bank for preprocessing and extracts the ITD cue via zero crossings (IID calculation is straight forward). The mapping between the cue values and the different angles is learned offline which facilitates the adaptation to different head geometries. The performance of the system is demonstrated by localization results for two simultaneous speakers and the mixture of a speaker, music, and fan noise in a normal meeting room. A real-time demonstrator of the system is presented in [1]. Index Terms: sound source localization, binaural, precedence effect, reverberant, echoic.

We propose a new approach for binaural sound source localization in real world environments implementing a new model of the precedence effect. This enables the robust measurement of the localization cue values (ITD, UD and IED) in echoic environments. The system is inspired by the auditory system of mammals. It uses a Gammatone filter bank for preprocessing and extracts the ITD and IED cues via zero crossings (UD calculation is straight forward). The mapping between the cue values and the different angles is learned offline which facilitates the adaptation to different head geometries. The performance of the system is demonstrated by localization results for two simultaneous speakers and the mixture of a speaker, music, and fan noise in a normal meeting room. A real time demonstrator of the system is presented in T. Rodemann, et al. (2006)

We present a sound localization system that operates in real-time, calculates three binaural cues (IED, UD, and ITD) and integrates them in a biologically inspired fashion to a combined localization estimation. Position information is furthermore integrated over frequency channels and time. The localization system controls a head motor to fovealize on and track the dominant sound source. Due to an integrated noise-reduction module the system shows robust localization capabilities even in noisy conditions. Real-time performance is gained by multi-threaded parallel operation across different machines using a timestamp-based synchronization scheme to compensate for processing delays