Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2023 | Book

Programming Primer Read chapter Read first chapter

Algorithmic Intelligence

Towards an Algorithmic Foundation for Artificial Intelligence

Author: Stefan Edelkamp

Publisher: Springer International Publishing

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

In this book the author argues that the basis of what we consider computer intelligence has algorithmic roots, and he presents this with a holistic view, showing examples and explaining approaches that encompass theoretical computer science and machine learning via engineered algorithmic solutions.

Part I of the book introduces the basics. The author starts with a hands-on programming primer for solving combinatorial problems, with an emphasis on recursive solutions. The other chapters in the first part of the book explain shortest paths, sorting, deep learning, and Monte Carlo search.

A key function of computational tools is processing Big Data efficiently, and the chapters in Part II of the book examine traditional graph problems such as finding cliques, colorings, independent sets, vertex covers, and hitting sets, and the subsequent chapters cover multimedia, network, image, and navigation data.

The highly topical research areas detailed in Part III are machine learning, problem solving, action planning, general game playing, multiagent systems, and recommendation and configuration.

Finally, in Part IV the author uses application areas such as model checking, computational biology, logistics, additive manufacturing, robot motion planning, and industrial production to explain how the techniques described may be exploited in modern settings.

The book is supported with a comprehensive index and references, and it will be of value to researchers, practitioners, and students in the areas of artificial intelligence and computational intelligence.

Table of Contents

Frontmatter

Basics

Frontmatter
Chapter 1. Programming Primer
Abstract
This chapter is a hands-on introduction to programming for solving combinatorial AI problems. The programming primer puts emphasis on recursive solutions. It is of didactic and practical value, providing insightful solutions to priority queue well-known problems.
Stefan Edelkamp
Chapter 2. Shortest Paths
Abstract
In state-space search the initial and the goal states are nodes in a graph. Edges between the nodes are labeled with cost. The task in single-source shortest path search is to find an optimal plan in the form of a sequence of edges that have the smallest cost total. In general graphs, the best-known algorithms are variants of Dijkstra’s approach. Nonetheless, after more than 50 years there are still many interesting cases in which it can be improved significantly.
Stefan Edelkamp
Chapter 3. Sorting
Abstract
Sorting a sequence of n elements probably is the most fascinating topic in computer science, and improved sorting implementations have significant impact for many applications like index calculations for databases.
Stefan Edelkamp
Chapter 4. Deep Learning
Abstract
The success in learning how to play Go at a professional level is based on training a deep neural network on a wider selection of human expert and self-playing games and poses the question on the availability, the limits, and the possibilities of this technique for other combinatorial games, especially, when there is a lack of access to a larger body of additional knowledge.
Stefan Edelkamp
Chapter 5. Monte-Carlo Search
Abstract
The purpose of statistical search algorithms, primarily Monte-Carlo search (MCS), is to make intelligent decisions, even (perhaps especially) in the absence of expert-designed heuristics. It does this by simulating a large number of random actions and using the statistics of the results to refine the decisions as more samples are made. Remarkably, this has been shown to work surprisingly well across a range of problems.
Stefan Edelkamp

Big Data

Frontmatter
Chapter 6. Graph Data
Abstract
The use of digital data has increased rapidly in the last few years. Traditional information sources like books, pictures, letters, or vinyls have been substituted by ebooks, digital photography, eMails, video, and audio. Big data is a wording that has been chosen to emphasize that this change is accompaigned by a rising amount of stored information. While the physical space is reduced, the information carried remains the same. Therefore, the selection, analysis, and evaluation of these amounts of data are important.
Stefan Edelkamp
Chapter 7. Multimedia Data
Abstract
In terms of big data, multimedia content in the form of digital audio and video is one of the fasted expanding sources. This is accelerated by the growing resolution on fixed and mobile devices and given that the infrastructure for filming is present on almost every smartphone in our pocket.
Stefan Edelkamp
Chapter 8. Network Data
Abstract
Probably the biggest amount of data these days is generated through the steadily increasing Internet traffic. Within this volume, incidents for network attacks have to be found and correlated.
Stefan Edelkamp
Chapter 9. Image Data
Abstract
We are addicted to the use of images, from personally taken shots, via magazines and scientific texts, to largescale advertisements. Visualization is inevitable, a picture tells more than a thousand words. The sheer number of digital pictures, however, often exceeds the memory capacity especially on modern handheld devices, so that they are often to be stored on specific storage devices or in the cloud. Even video data is often reduced to the analysis of keyframes.
Stefan Edelkamp
Chapter 10. Navigation Data
Abstract
Urban mobility planning depends largely on the presence of good navigation data. Vector maps are not always available for many areas – especially for many of the third world countries. On the other hand, good paper maps collected by the city authorities are widely available. A solution is the collaborative map generation process that allows people to share the collected GPS traces. Nevertheless, the integration of these GPS traces is itself a challenge and requires a good base map.
Stefan Edelkamp

Research Areas

Frontmatter
Chapter 11. Machine Learning
Abstract
In previous chapters we already looked at different machine learning problems. In Chapter 4 we introduced the concept of multi-layered and convolutional neural nets, as well as the limits and possibilities of deep learning. In Chapter 5 we have investigated randomized search algorithms for reinforcement learning, where the payoff in the rollouts is backpropagated to improve action selection. In Chapter 8 we looked at predicting time series and the problem of probabilistic inference based on background knowledge. Chapter 9 considered improvements to nearest neighbor search and classification with support vector machines for computer vision tasks. Last, but not least, in Chapter 10 we incrementally learnt a map based on incoming GPS traces.
Stefan Edelkamp
Chapter 12. Problem Solving
Abstract
This work will merge two different lines of research, namely state-space search with binary decision diagrams (BDDs), that was initially proposed for Model Checking and still is state of the art in AI Planning; and statespace compaction with (minimal) perfect hashing, which is used in the algorithm community as a memory-based index for big data (often residing on disk).
Stefan Edelkamp
Chapter 13. Card Game Playing
Abstract
One central showcase of algorithmic intelligence is to prove that computers are able to beat humans in games. As many board games have either been solved or AIs show superhuman performance one of the next AI challenges are card games with randomness in the deal and incomplete information due to cards being hidden. While there is impressive research on playing multi-player non-cooperative card games like Poker, for cooperative card games like Skat or Bridge, humans were experienced to play better than computers.
Stefan Edelkamp
Chapter 14. Action Planning
Abstract
Action planning is an act of general problem solving. Given a textual representation of initial state, goal conditions and actions, the task is to find a plan in form of a sequence of action that solves the problem. As action planners are often used as problem solving prototypes, good performance is crucial.
Stefan Edelkamp
Chapter 15. General Game Playing
Abstract
In recent years, general game playing has received an increasing amount of attention. In general game playing the agents are provided a description of a game according to certain rules and need to play it. General game playing also allows us to express multi-player games and supports any number of participants. In case of multiplayer games, the agents often play against each other, while in case of single-player games one agent tries to find a way to reach a terminal state where it can achieve the best reward possible. The authors of the agents do not know which games will be played, so no domain-specific knowledge can be inserted. In general game playing the players only get rewards for achieving goals: for each possible terminal state the player is awarded points ranging from 0 (worst) to 100 (best).
Stefan Edelkamp
Chapter 16. Multiagent Systems
Abstract
This chapter considers multiagent systems and their simulation. It documents the outcome of a study for addressing last-mile connectivity within a multiagent simulation system.We report on the simulation setup and the outcome in form of a feasibility assessment. The study provides a description of the agent model and its routing infrastructure as a step towards a rich model of the interactions that happen in urban mobility. We implement a scenario starting on a higher level of abstraction, drilling down to a running program. The multiagent model is generic in the sense that different transport agencies and vehicles can be added. It integrates planning with execution, a hot research topic these days.We will encounter that a sequence of calls to Dijkstra’s single-source shortest-paths algorithm is crucial for planning and use an efficient implementation with radix heaps.
Stefan Edelkamp
Chapter 17. Recommendation and Configuration
Abstract
In Chapter 11 matrix factorizations were studied. In this chapter we first look at recommendation and its relation to clustering. We explain how general the method is and how it attacks the curse of dimensionality. We review the problem of bitvector classification, going forward to clustering, and explain pathological behaviors of current algorithms have.
Stefan Edelkamp

Applications

Frontmatter
Chapter 18. Adversarial Planning
Abstract
Effective and efficient reasoning in adversarial environments is important for many real-world applications, ranging from cybersecurity to military operations. Deliberative reasoning techniques, such as automated planning, are often restricted to static environments where only one agent can make changes through his/her actions.
Stefan Edelkamp
Chapter 19. Model Checking
Abstract
Model checking is the automated process of checking the correctness of one piece of software with another one. Due to uncertainty of its execution order or of its inputs, the system under consideration shows non-deterministic behavior. As the general problem of checking correctness is undecidable, model checking often resorts to validating compliance with respect to temporal specification.
Stefan Edelkamp
Chapter 20. Computational Biology
Abstract
In this chapter we solve the multiple sequence alignment problem, a combinatorial challenge in computational biology, where several DNA, RNA, or protein sequences interpreted as strings are to be arranged for high similarity. The proposal applies randomized Monte-Carlo tree search with nested rollouts and can improve the solution quality over time. Instead of learning the position of the letters, the approach learns a policy for the position of the gaps. The Monte-Carlo beam search algorithm we use has a low memory overhead and can be invoked with constructed or known initial solutions. Experiments show promising results in improving existing alignments.
Stefan Edelkamp
Chapter 21. Logistics
Abstract
The dynamics and complexity of planning and scheduling processes in groupage traffic require efficient, proactive, and reactive system behavior to improve the service quality while ensuring time and cost-efficient transportation. At first, we, therefore, implement a multiagent system to emerge an adequate system behavior and focus on the decision-making processes of agents that is based on the Traveling Salesman Problem (TSP) with aspects like contract time windows, individual restricted capacities of trucks, premium services and varying priorities of dynamically incoming orders. We present an optimal depth-first branch-and-bound asymmetric TSP solver with constraints on tour feasibility and depot reachability at any step of the process. We use established benchmarks as well as its inclusion in a real-life multiagent-based simulation. Simulated scenarios are based on real customer orders and are applied on real-world infrastructures. The results reveal that efficient optimal decision making in multiagent systems increases the service quality and meets the requirements and challenges in logistics.
Stefan Edelkamp
Chapter 22. Additive Manufacturing
Abstract
This chapter considers solving a problem in combinatorial search: the automated arrangement of irregularshaped objects for industrial 3D printing. The input is a set of triangulated models; the output is a set of location and orientation vectors for the objects. The algorithm consists of three stages: 1) translation of the models into an octree; 2) design of an efficient test for pairwise intersection based on sphere trees; and 3) computation of an optimized placement of the objects using simulated annealing. We compare several sphere-tree construction methods and annealing parameter settings to derive valid packings.
Stefan Edelkamp
Chapter 23. Robot Motion Planning
Abstract
Motion planning aims to increase the ability of robots to plan and act on their own. Efficient and safe motion planning algorithms are crucial for the applications of robots in life and industry. One of the most developed motion planning for these requirements is sampling-based motion planning, such as rapidly exploring random trees (RRT), and its improvement RRT*.
Stefan Edelkamp
Chapter 24. Industrial Production
Abstract
A discrete event system (DES) is a dynamic system with discrete states and transitions, which are triggered by events. We apply a software model checker to a discrete event system that controls the industrial production of autonomous products. The flow of material is asynchronous and buffered. This chapter aims to find concurrent plans that optimize the throughput of the system. In mapping the discrete event system directly to the model checker, we model the production line as a set of communicating processes, with the movement of items modeled as channels. Experiments show that the model checker can analyze the DES, subject to the partial ordering of the product parts. It derives valid and optimized plans with several thousands of steps using constrained branch-and-bound.
Stefan Edelkamp
Chapter 25. Further Application Areas
Abstract
What is AI? In an industrial context you will hear the ones saying a threat to the world by thinking machines superior to humans, or other stating storing a number in the computer means that the machine has learnt. We think both statements, reflecting either a strong or a weak view on AI, are not pragmatic. In this book we, therefore, align with an efficiency- and performance-oriented interpretation of AI, which we denote as Algorithmic Intelligence. The very same AI can beat a human in a competition on a fast machine, and lose on a slower one.
Stefan Edelkamp
Backmatter
Metadata
Title
Algorithmic Intelligence
Author
Stefan Edelkamp
Copyright Year
2023
Electronic ISBN
978-3-319-65596-3
Print ISBN
978-3-319-65595-6
DOI
https://doi.org/10.1007/978-3-319-65596-3

Premium Partner

    Image Credits