Human-Centered Algorithm Engineering

The HumAlgo project aims to develop and establish an entirely new approach in algorithmics, a central research area of computer science. Algorithmics is an area of theoretical computer science that employs formal, mathematical methods to design and analyze algorithms, which form the core of all software that shapes todays digital world. One point of criticism that faced algorithm theory in the past is a lack of relevance to practice. The methodology of algorithm engineering is a means to counteract this criticism. Algorithm engineering complements formal design and analysis with implementation aspects of algorithms and their experimental evaluation. Yet, many complex tasks that ask for software-aided solutions, cannot be transformed without clear limitations into a formal, algorithmic model to be solved in the sense of the algorithm engineering method. Examples can be found in the areas of network visualization and cartography, where aesthetic and subjective criteria determine solution quality and where professional graphic designers usually create better solutions than traditional computer programs that lack human creativity and superior cognitive skills. Computational questions, where humans fail when faced with the amount of data and computers fail due to insufficient models, are at the core of this project. For these kinds of problems, we want to complement the algorithm engineering methodology by integrating human expertise and creativity into algorithmic solution processes. Our main hypothesis is that this allows to design interactive human-machine algorithms that lead to more efficient, higher quality and better comprehensible solutions for human (expert) users. To achieve this, we integrate human constraints and needs in addition to formal problem modeling from the very beginning of the algorithm design process and evaluate the resulting algorithms and their solutions together with domain experts and compared against fully automatic as well as against manual solutions. Using selected application problems as examples, our goal in this project is to obtain novel interactive algorithms that combine the computing power of computers with the creativity and experience of human experts. In addition, we want to use the knowledge gained from these examples to develop the theoretical foundations of this so-called human-centered algorithm engineering and thus establish a new methodology for a whole class of computational problems, whose successful solution asks for combining the skills of human and machine.

Efficient algorithms play a fundamental role in the wide range of intelligent systems and software applications driving our modern, digitalized world. While fully automated solutions are perfectly fine in many cases, there are also a lot of highly relevant applications, where humans must or should interact with computer systems to find high-quality solutions that best fit a certain demand. This is the case especially when there is not a unique and formally defined optimization goal, but rather a diverse mix of soft criteria that characterize solution quality in a less crisp way. The ultimate choice of a solution may then be up to human judgment and subjective preferences. This FWF stand-alone project "Human-centered Algorithm Engineering" targeted the study of the latter type of computational problems. The project team aimed for designing and engineering algorithms for interactive human-computer co-optimization. Our main research challenge was to efficiently and effectively combine the mathematical accuracy and computational power of formal algorithmics with the creative power of the human mind. In this project, we chose two important research areas to apply this new algorithmic paradigm: Network visualization and computational cartography. Both fields have in common that they study visual, geometric representations of complex data with an aim for high legibility and aesthetic appeal - two criteria that are difficult to quantify and that involve a lot of subjective human judgment by domain experts. In the results obtained in this project, we thoroughly investigated interactive algorithms from both a theoretical perspective and a practical algorithm engineering perspective. For the more theoretical considerations, we studied different dynamic optimization algorithms that can iteratively solve user-constrained computational problems by acting on hypothetical user input and taking into account the visual stability of a sequence of intermediate solutions. These algorithms are specifically aimed for consistent solution updates with faster computation times compared to re-computations from scratch. For the more practical questions, we implemented a variety of interactive algorithms and evaluated their performance both by quantitative simulation experiments and by human-subject studies. Our application topics ranged from biological network data visualization, to semantic word clouds in text visualization and from labeling map features to cartograms and schematic network maps. Overall, the project led to two successfully defended PhD theses and a collection of 39 peer-reviewed research papers presented in scientific journals and conferences.