Airports and their related operations have become the major bottlenecks to the entire air traffic management system, raising predictability, safety, and environmental concerns. One of the underpinning techniques for digital and sustainable air transport is airport ground movement optimization. Currently, real ground movement data is made freely available for the majority of aircraft at many airports. However, the recorded data is not accurate enough due to measurement errors and general uncertainties. In this article, we aim to develop a new interval type-2 fuzzy logic-based map matching algorithm, which can match each raw data point to the correct airport segment. To this aim, we first specifically design a set of interval type-2 Sugeno fuzzy rules and their associated rule weights, as well as the model output, based on preliminary experiments and sensitivity tests. Then, the fuzzy membership functions are fine-tuned by a particle swarm optimization algorithm. Moreover, an extra checking step using the available data is further integrated to improve map matching accuracy. Using the real-world aircraft movement data at Hong Kong airport, we compared the developed algorithm with other well known map matching algorithms. Experimental results show that the designed interval type-2 fuzzy rules have the potential to handle map matching uncertainties, and the extra checking step can effectively improve map matching accuracy. The proposed algorithm is demonstrated to be robust and achieve the best map matching accuracy of over 96% without compromising the run time.

Automatic program repair (APR) is a rapidly advancing field of software engineering that aims to supplement or replace manual bug fixing with an automated tool. For APR to be successfully adopted in industry, it is vital that APR tools respond to developer needs and preferences. However, very little research has considered developers' general attitudes to APR or developers' current bug fixing practices (the activity APR aims to replace). This paper responds to this gap by reporting on a survey of 386 software developers about their bug finding and fixing practices and experiences, and their instinctive attitudes towards APR. We find that bug finding and fixing is not necessarily as onerous for developers as has often been suggested, being rated as more satisfying than developers' general work. The fact that developers derive satisfaction and benefit from bug fixing indicates that APR adoption is not as simple as APR replacing an unwanted activity. When it comes to potential APR approaches, we find a strong preference for developers being kept in the loop (for example, choosing between different fixes or validating fixes) as opposed to a fully automated process. This suggests that advances in APR should be careful to consider the agency of the developer, as well as what information is presented to developers alongside fixes. It also indicates that there are key barriers related to trust that would need to be overcome for full scale APR adoption, supported by the fact that even those developers who stated that they were positive about APR listed several caveats and concerns. We find very few statistically significant relationships between particular demographic variables (for example, developer experience, age, education) and key attitudinal variables, suggesting that developers' instinctive attitudes towards APR are little influenced by experience level but are held widely across the developer community.

Automatic program repair (APR) offers significant potential for automating some coding tasks. Using APR could reduce the high costs historically associated with fixing code faults and deliver significant benefits to software engineering. Adopting APR could also have profound implications for software developers’ daily activities, transforming their work practices. To realise the benefits of APR it is vital that we consider how developers feel about APR and the impact APR may have on developers’ work. Developing APR tools without consideration of the developer is likely to undermine the success of APR deployment. In this paper, we critically review how developers are considered in APR research by analysing how human factors are treated in 260 studies from Monperrus’s Living Review of APR. Over half of the 260 studies in our review were motivated by a problem faced by developers (e.g., the difficulty associated with fixing faults). Despite these human-oriented motivations, fewer than 7% of the 260 studies included a human study. We looked in detail at these human studies and found their quality mixed (for example, one human study was based on input from only one developer). Our results suggest that software developers are often talkedaboutin APR studies, but are rarely talkedwith. A more comprehensive and reliable understanding of developer human factors in relation to APR is needed. Without this understanding, it will be difficult to develop APR tools and techniques which integrate effectively into developers’ workflows. We recommend a future research agenda to advance the study of human factors in APR.

In this short paper, we explore the Pareto principle, sometimes known as the “80-20” rule as part of the refactoring process. We explore five frequently applied refactorings, namely extract method, extract variable, rename variable, rename method and change variable type from a data set of forty open-source systems and nearly two hundred thousand refactorings. We address two key research questions. Firstly, do 80% of “buggy” refactorings (where a refactoring has induced a bug fix) arise from just 20% of commits and, secondly, does the same rule apply to “non-buggy” refactorings when applied to the same systems? To facilitate our analysis, we used refactoring and bug data from a study by Di Penta et al. Results showed that refactorings inducing bugs were clustered around a more concentrated set of commits than refactorings that did not induce bugs. One refactoring ‘change variable type’ stood out - it almost conformed to an 80-20 rule. The take-away message is, as the saying goes, that too much of a “good” thing [refactoring] could actually be a “bad” thing.

This paper reports on qualitative research into automatic program repair (APR) at Bloomberg. Six focus groups were conducted with a total of seventeen participants (including both developers of the APR tool and developers using the tool) to consider: the development at Bloomberg of a prototype APR tool (Fixie); developers’ early experiences using the tool; and developers’ perspectives on how they would like to interact with the tool in future. APR is developing rapidly and it is important to understand in greater detail developers' experiences using this emerging technology. In this paper, we provide in-depth, qualitative data from an industrial setting. We found that the development of APR at Bloomberg had become increasingly user-centered, emphasising how fixes were presented to developers, as well as particular features, such as customisability. From the focus groups with developers who had used Fixie, we found particular concern with the pragmatic aspects of APR, such as how and when fixes were presented to them. Based on our findings, we make a series of recommendations to inform future APR development, highlighting how APR tools should 'start small', be customisable, and fit with developers' workflows. We also suggest that APR tools should capitalise on the promise of repair bots and draw on advances in explainable AI.

Yujian Gan, Xinyun Chen, Qiuping Huang, Matthew Purver, John R. Woodward, Jinxia Xie, Pengsheng Huang. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

Automatic Program Repair (APR) has been proposed to help developers and reduce the time spent repairing programs. Recent APR tools have applied learned templates (fix patterns) to fix code using knowledge from fixes successfully applied in the past. However, there is still no general agreement on the representation of fix patterns, making their application and comparison with a baseline difficult. As a consequence, it is also difficult to expand fix patterns and further enable APR. We automatically generate fix patterns from similar fixes and compare the generated fix patterns against a state-of-the-art taxonomy. Our automated approach splits fixes into smaller, method-level chunks and calculates their similarity. A threshold-based clustering algorithm groups similar chunks and finds matches with state-of-the-art fix patterns. In our evaluation, we present 33 clusters whose fix patterns were generated from the fixes of 835 Defects4J bugs. Of those 33 clusters, 22 matched a state-of-the-art taxonomy with good agreement. The remaining 11 clusters were thematically analysed and generated new fix patterns that expanded the taxonomy. Our new fix patterns should enable APR researchers and practitioners to expand their tools to fix a greater range of bugs in the future.

This paper introduces a computer-game design tool which enables game designers to explore and develop game mechanics for arbitrary game systems. The tool is implemented as a plugin for the Godot game engine. It allows the designer to view an abstraction of a game's states while in active development and to quickly view and explore which states are navigable from which other states. This information is used to rapidly explore, validate and improve the design of the game. The tool is most practical for game systems which are computer-explorable within roughly 2000 states. The tool is demonstrated by presenting how it was used to create a small, yet complete, commercial game.

In this paper, we introduce a technique for data augmentation that has been applied to an ECG dataset from the UKBiobank for heart arrhythmia classification using the XGBoost algorithm. In the majority of clinical datasets, the number of participants with a disease (positive samples) is considerably lower than the number of healthy participants (negative samples). Hence, when it comes to using the data in machine learning, there are not enough cases of the diseased participants for the algorithm to train a model. We have developed techniques to overcome this limitation by up-sampling the positive cases. To validate our technique we have evaluated its reliability by comparing the augmented data set with the original data distribution using the Wilcoxon signed rank statistical significance test. We have also compared the results with and without data augmentation on the XGBoost classifier, and have used the AUC (area under the curve) and the Cohen's Kappa as the evaluation metrics. In our results, the AUC improved from 0.58 without augmentation to 0.83 with augmentation and the Cohen's kappa improved from 0 to 0.76. Our metrics values show the agreement is substantial. These techniques can be used on any other data and are not limited to clinical studies.

In some cases, heuristics may be transferred easily between different optimisation problems. This is the case if these problems are equivalent or dual (e.g., maximum clique and maximum independent set) or have similar objective functions. However, the link between problems can further be defined by the constraints that define them. This refining can be achieved by organising constraints into families and translating between them using gadgets. If two problems are in the same constraint family, the gadgets tell us how to map from one problem to another and which constraints are modified. This helps better understand a problem through its constraints and how best to use domain specific heuristics. In this position paper, we argue that this allows us to understand how to map between heuristics developed for one problem to heuristics for another problem, giving an example of how this might be achieved.

There are few digital tools to help designers create game mechanics. A general language to express game mechanics is necessary for rapid game design iteration. The first iteration of a mechanics-focused language, together with its interfacing tool, are introduced in this paper. The language is restricted to two-dimensional, turn-based, tile-based, deterministic, complete-information games. The tool is compared to the existing alternatives for game mechanics prototyping and shown to be capable of succinctly implementing a range of well-known game mechanics.

In this paper, we present PlayMapper, a novel variant of the MAP-Elites algorithm that has been adapted to map the level design space of the Super Mario Bros game. Our approach uses player and level based features to create a map of playable levels. We conduct an experiment to compare the effect of different sets of input features on the range of levels generated using this technique. In this work, we show that existing search-based techniques for PCG can be improved to allow for more control and creative freedom for designers. Current limitations of the system and directions for future work are also discussed.

In this paper, we use preference learning techniques to model players’ emotional preferences in an AR mobile game. This exploratory study uses player behaviour to make these preference predictions. The described techniques successfully predict players’ frustration and challenge levels with high accuracy while all other preferences tested (boredom, excitement and fun) perform better than random chance. This paper describes the AR treasure hunt game we developed, the user study conducted to collect player preference data, analysis performed, and preference learning techniques applied to model this data. This work is motivated to personalize players’ experiences by using these computational models to optimize content creation and game balancing systems in these environments. The generality of our technique, limitations, and usability as a tool for personalization of AR mobile games is discussed.

With increasing demand for air travel and overloaded airport facilities, inefficient airport taxiing operations are a significant contributor to unnecessary fuel burn and a substantial source of pollution. Although taxiing is only a small part of a flight, aircraft engines are not optimised for taxiing speed and so contribute disproportionately to the overall fuel burn. Delays in taxiing also waste scarce airport resources and frustrate passengers. Consequently, reducing the time spent taxiing is an important investment. An exact algorithm for finding shortest paths based on A* allocates routes to aircraft that maintains aircraft at a safe distance apart, has been shown to yield efficient taxi routes. However, this approach depends on the order in which aircraft are chosen for allocating routes. Finding the right order in which to allocate routes to the aircraft is a combinatorial optimization problem in itself.

Genetic improvement (GI) uses automated search to find improved versions of existing software. We present a comprehensive survey of this nascent field of research with a focus on the core papers in the area published between 1995 and 2015. We identified core publications including empirical studies, 96% of which use evolutionary algorithms (genetic programming in particular). Although we can trace the foundations of GI back to the origins of computer science itself, our analysis reveals a significant upsurge in activity since 2012. GI has resulted in dramatic performance improvements for a diverse set of properties such as execution time, energy and memory consumption, as well as results for fixing and extending existing system functionality. Moreover, we present examples of research work that lies on the boundary between GI and other areas, such as program transformation, approximate computing, and software repair, with the intention of encouraging further exchange of ideas between researchers in these fields.

With the expanding load on healthcare and consequent strain on budget, the demand for tools to increase efficiency in treatments is rising. The use of prediction models throughout the treatment to identify risk factors might be a solution. In this paper we present a novel implementation of a prediction tool and the first use of a dynamic predictor in vocational rehabilitation practice. The tool is periodically updated and improved with Genetic Improvement of software. The predictor has been in use for 10 months and is evaluated on predictions made during that time by comparing them with actual treatment outcome. The results show that the predictions have been consistently accurate throughout the patients' treatment. After approximately 3 week learning phase, the predictor classified patients with 100% accuracy and precision on previously unseen data. The predictor is currently being successfully used in a complex live system where specialists have used it to make informed decisions.

In this study we use Genetic Programming (GP) as an offline hyper-heuristic to evolve a mutation operator for Evolutionary Programming. This is done using the Gaussian and uniform distributions as the terminal set, and arithmetic operators as the function set. The mutation operators are automatically designed for a specific function class. The contribution of this paper is to show that a GP can not only automatically design a mutation operator for Evolutionary Programming (EP) on functions generated from a specific function class, but also can design more general mutation operators on functions generated from groups of function classes. In addition, the automatically designed mutation operators also show good performance on new functions generated from a specific function class or a group of function classes.

The literature shows that one-, two-, and three-dimensional bin packing and knapsack packing are difficult problems in operational research. Many techniques, including exact, heuristic, and metaheuristic approaches, have been investigated to solve these problems and it is often not clear which method to use when presented with a new instance. This paper presents an approach which is motivated by the goal of building computer systems which can design heuristic methods. The overall aim is to explore the possibilities for automating the heuristic design process. We present a genetic programming system to automatically generate a good quality heuristic for each instance. It is not necessary to change the methodology depending on the problem type (one-, two-, or three-dimensional knapsack and bin packing problems), and it therefore has a level of generality unmatched by other systems in the literature. We carry out an extensive suite of experiments and compare with the best human designed heuristics in the literature. Note that our heuristic design methodology uses the same parameters for all the experiments. The contribution of this paper is to present a more general packing methodology than those currently available, and to show that, by using this methodology, it is possible for a computer system to design heuristics which are competitive with the human designed heuristics from the literature. This represents the first packing algorithm in the literature able to claim human competitive results in such a wide variety of packing domains.

We present a genetic programming (GP) system to evolve reusable heuristics for the 2-D strip packing problem. The evolved heuristics are constructive, and decide both which piece to pack next and where to place that piece, given the current partial solution. This paper contributes to a growing research area that represents a paradigm shift in search methodologies. Instead of using evolutionary computation to search a space of solutions, we employ it to search a space of heuristics for the problem. A key motivation is to investigate methods to automate the heuristic design process. It has been stated in the literature that humans are very good at identifying good building blocks for solution methods. However, the task of intelligently searching through all of the potential combinations of these components is better suited to a computer. With such tools at their disposal, heuristic designers are then free to commit more of their time to the creative process of determining good components, while the computer takes on some of the design process by intelligently combining these components. This paper shows that a GP hyper-heuristic can be employed to automatically generate human competitive heuristics in a very-well studied problem domain.

We present a novel algorithm for the one- dimension offline bin packing problem with discrete item sizes based on the notion of matching the item-size histogram with the bin-gap histogram. The approach is controlled by a constructive heuristic function which decides how to prioritise items in order to minimise the difference between histograms. We evolve such a function using a form of linear register-based genetic programming system. We test our evolved heuristics and compare them with hand-designed ones, including the well- known best fit decreasing heuristic. The evolved heuristics are human-competitive, generally being able to outperform high- performance human-designed heuristics.

It is possible to argue that online bin packing heuristics should be evaluated by using metrics based on their performance over the set of all bin packing problems, such as the worst case or average case performance. However, this method of assessing a heuristic would only be relevant to a user who employs the heuristic over a set of problems which is actually representative of the set of all possible bin packing problems. On the other hand, a real world user will often only deal with packing problems that are representative of a particular sub-set. Their piece sizes will all belong to a particular distribution. The contribution of this paper is to show that a Genetic Programming system can automate the process of heuristic generation and produce heuristics that are human-competitive over a range of sets of problems, or which excel on a particular sub-set. We also show that the choice of training instances is vital in the area of automatic heuristic generation, due to the trade-off between the performance and generality of the heuristics generated and their applicability to new problems.

Standard GP, chiefly concerned with evolving functions, which are mappings from inputs to output, is not Turing Complete. We raise issues resulting from attempts at extending standard GP to Turing Complete representations. Firstly, there is a problem when a contiguous piece of code is moved to a new location (in a different program) by crossover. In general its functionality will be altered if global memory is used, as other parts of the program may access the same piece of memory. Secondly, traditional crossover does not respect modules. Crossover can disrupt a group of instructions that were working together (e.g. in the body of a loop) in one parent, but end up separated in two different offspring after reproduction. A crossover operator is proposed that only operates at the boundaries of modules. The identification of module boundaries is made easy by using a representation in which explicit modules are denned, in contrast with other representations where the module boundaries would have to be identified by some other means. The halting problem is a central issue, however as a consequence of this crossover operator we are more likely to produce self terminating programs, thus saving time when testing.

Genetic algorithms (GAs) and genetic programming (GP) are often considered as separate but related fields. Typically, GAs use a fixed length linear representation, whereas GP uses a variable size tree representation. This paper argues that the differences are unimportant. Firstly, variable length actually means variable length up to some fixed limit, so can really be considered as fixed length. Secondly, the representations and genetic operators of GA and GP appear different, however ultimately it is a population of bit strings in the computers memory which is being manipulated whether it is GA or GP which is being run on the computer. The important difference lies in the interpretation of the representation; if there is a one to one mapping between the description of an object and the object itself (as is the case with the representation of numbers), or a many to one mapping (as is the case with the representation of programs). This has ramifications for the validity of the No Free Lunch theorem, which is valid in the first case but not in the second. It is argued that due to the highly related nature of GAs and GP, that many of the empirical results discovered in one field will apply to the other field, for example maintaining high diversity in a population to improve performance.