| 1. |
- Nikko, Erik, et al.
(författare)
-
Towards Verification and Validation of Reinforcement Learning in Safety-Critical Systems : A Position Paper from the Aerospace Industry
- 2021
-
Ingår i: Robust and Reliable Autonomy in the Wild, International Joint Conferences on Artificial Intelligence.
-
Konferensbidrag (refereegranskat)abstract
- Reinforcement learning techniques have successfully been applied to solve challenging problems. Among the more famous examples are playing games such as Go and real-time computer games such as StarCraft II. In addition, reinforcement learning has successfully been deployed in cyber-physical systems such as robots playing a curling-based game. These are all important and significant achievements indicating that the techniques can be of value for the aerospace industry. However, to use these techniques in the aerospace industry, very high requirements on verification and validation must be met. In this position paper, we outline four key problems for verification and validation of reinforcement learning techniques. Solving these are an important step towards enabling reinforcement learning techniques to be used in safety critical domains such as the aerospace industry.
|
|
| 2. |
- Präntare, Fredrik, 1990-
(författare)
-
Dividing the Indivisible : Algorithms, Empirical Advances, and Complexity Results for Value-Maximizing Combinatorial Assignment Problems
- 2024
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Allocating resources, goods, agents (e.g., humans), expertise, production, and assets is one of the most influential and enduring cornerstone challenges at the intersection of artificial intelligence, operations research, politics, and economics. At its core—as highlighted by a number of seminal works [181, 164, 125, 32, 128, 159, 109, 209, 129, 131]—is a timeless question: How can we best allocate indivisible entities—such as objects, items, commodities, jobs, or personnel—so that the outcome is as valuable as possible, be it in terms of expected utility, fairness, or overall societal welfare? This thesis confronts this inquiry from multiple algorithmic viewpoints, focusing on the value-maximizing combinatorial assignment problem: the optimization challenge of partitioning a set of indivisibles among alternatives to maximize a given notion of value. To exemplify, consider a scenario where an international aid organization is responsible for distributing medical resources, such as ventilators and vaccines, and allocating medical personnel, including doctors and nurses, to hospitals during a global health crisis. These resources and personnel—inherently indivisible and non-fragmentable—necessitate an allocation process designed to optimize utility and fairness. Rather than using manual interventions and ad-hoc methods, which often lack precision and scalability, a rigorously developed and demonstrably performant approach can often be more desirable. With this type of challenge in mind, our thesis begins through the lens of computational complexity theory, commencing with an initial insight: In general, under prevailing complexity-theoretic assumptions (P ≠ NP), it is impossible to develop an efficient method guaranteeing a value-maximizing allocation that is better than “arbitrarily bad”, even under severely constraining limitations and simplifications. This inapproximability result not only underscores the problem’s complexity but also sets the stage for our ensuing work, wherein we develop novel algorithms and concise representations for utilitarian, egalitarian, and Nash welfare maximization problems, aimed at maximizing average, equitable, and balanced utility, respectively. For example, we introduce the synergy hypergraph—a hypergraph-based characterization of utilitarian combinatorial assignment—which allows us to prove several new state-of-the-art complexity results to help us better understand how hard the problem is. We then provide efficient approximation algorithms and (non-trivial) exponential-time algorithms for many hard cases. In addition, we explore complexity bounds for generalizations with interdependent effects between allocations, known as externalities in economics. Natural applications in team formation, resource allocation, and combinatorial auctions are also discussed; and a novel “bootstrapped” dynamic-programming method is introduced. We then transition from theory to practice as we shift our focus to the utilitarian variant of the problem—an incarnation of the problem particularly applicable to many real-world scenarios. For this variation, we achieve substantial empirical algorithmic improvements over existing methods, including industry-grade solvers. This work culminates in the development of a new hybrid algorithm that combines dynamic programming with branch-and-bound techniques that is demonstrably faster than all competing methods in finding both optimal and near-optimal allocations across a wide range of experiments. For example, it solves one of our most challenging problem sets in just 0.25% of the time required by the previous best methods, representing an improvement of approximately 2.6 orders of magnitude in processing speed. Additionally, we successfully integrate and commercialize our algorithm into Europa Universalis IV—one of the world’s most popular strategy games, with a player base exceeding millions. In this dynamic and challenging setting, our algorithm efficiently manages complex strategic agent interactions, highlighting its potential to improve computational efficiency and decision-making in real-time, multi-agent scenarios. This also represents one of the first instances where a combinatorial assignment algorithm has been applied in a commercial context. We then introduce and evaluate several highly efficient heuristic algorithms. These algorithms—while lacking provable quality guarantees—employ general-purpose heuristic and random-sampling techniques to significantly outperform existing methods in both speed and quality in large-input scenarios. For instance, in one of our most challenging problem sets, involving a thousand indivisibles, our best algorithm generates outcomes that are 99.5% of the expected optimal in just seconds. This performance is particularly noteworthy when compared to state-of-the-art industry-grade solvers, which struggle to produce any outcomes under similar conditions. Further advancing our work, we employ novel machine learning techniques to generate new heuristics that outperform the best hand-crafted ones. This approach not only showcases the potential of machine learning in combinatorial optimization but also sets a new standard for combinatorial assignment heuristics to be used in real-world scenarios demanding rapid, high-quality decisions, such as in logistics, real-time tactics, and finance. In summary, this thesis bridges many gaps between the theoretical and practical aspects of combinatorial assignment problems such as those found in coalition formation, combinatorial auctions, welfare-maximizing resource allocation, and assignment problems. It deepens the understanding of the computational complexities involved and provides effective and improved solutions for longstanding real-world challenges across various sectors—providing new algorithms applicable in fields ranging from artificial intelligence to logistics, finance, and digital entertainment, while simultaneously paving the way for future work in computational problem-solving and optimization.
|
|
| 3. |
- Präntare, Fredrik, 1990-, et al.
(författare)
-
Hybrid Dynamic Programming for Simultaneous Coalition Structure Generation and Assignment
- 2021
-
Ingår i: PRIMA 2020: Principles and Practice of Multi-Agent Systems. - Cham : Springer. - 9783030693220 - 9783030693213 ; , s. 19-33
-
Konferensbidrag (refereegranskat)abstract
- We present, analyze and benchmark two algorithms for simultaneous coalition structure generation and assignment: one based entirely on dynamic programming, and one anytime hybrid approach that uses branch-and-bound together with dynamic programming. To evaluate the algorithms’ performance, we benchmark them against both CPLEX (an industry-grade solver) and the state-of-the-art using difficult randomized data sets of varying distribution and complexity. Our results show that our hybrid algorithm greatly outperforms CPLEX, pure dynamic programming and the current state-of-the-art in all of our benchmarks. For example, when solving one of the most difficult problem sets, our hybrid approach finds optimum in roughly 0.1% of the time that the current best method needs, and it generates 98% efficient interim solutions in milliseconds in all of our anytime benchmarks; a considerable improvement over what previous methods can achieve.
|
|
| 4. |
- Präntare, Fredrik, 1990-, et al.
(författare)
-
Towards Utilitarian Combinatorial Assignment with Deep Neural Networks and Heuristic Algorithms
- 2020
-
Konferensbidrag (refereegranskat)abstract
- This paper presents preliminary work on using deep neural networksto guide general-purpose heuristic algorithms for performing utilitarian combinatorial assignment. In more detail, we use deep learning in an attempt to produce heuristics that can be used together with e.g., search algorithms to generatefeasible solutions of higher quality more quickly. Our results indicate that ourapproach could be a promising future method for constructing such heuristics.
|
|
| 5. |
- Bonte, Pieter, et al.
(författare)
-
Grounding Stream Reasoning Research
- 2024
-
Ingår i: Transactions on Graph Data and Knowledge (TGDK). - Wadern, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. - 2942-7517. ; 2:1, s. 1-47
-
Tidskriftsartikel (refereegranskat)abstract
- In the last decade, there has been a growing interest in applying AI technologies to implement complex data analytics over data streams. To this end, researchers in various fields have been organising a yearly event called the "Stream Reasoning Workshop" to share perspectives, challenges, and experiences around this topic.In this paper, the previous organisers of the workshops and other community members provide a summary of the main research results that have been discussed during the first six editions of the event. These results can be categorised into four main research areas: The first is concerned with the technological challenges related to handling large data streams. The second area aims at adapting and extending existing semantic technologies to data streams. The third and fourth areas focus on how to implement reasoning techniques, either considering deductive or inductive techniques, to extract new and valuable knowledge from the data in the stream.This summary is written not only to provide a crystallisation of the field, but also to point out distinctive traits of the stream reasoning community. Moreover, it also provides a foundation for future research by enumerating a list of use cases and open challenges, to stimulate others to join this exciting research area.
|
|
| 6. |
- Engelsons, Daniel, et al.
(författare)
-
Coverage Path Planning in Large-scale Multi-floor Urban Environments with Applications to Autonomous Road Sweeping
- 2022
-
Ingår i: 2022 International Conference on Robotics and Automation (ICRA). - : Institute of Electrical and Electronics Engineers (IEEE). - 9781728196817 - 9781728196824 ; , s. 3328-3334
-
Konferensbidrag (refereegranskat)abstract
- Coverage Path Planning is the work horse of contemporary service task automation, powering autonomous floor cleaning robots and lawn mowers in households and office sites. While steady progress has been made on indoor cleaning and outdoor mowing, these environments are small and with simple geometry compared to general urban environments such as city parking garages, highway bridges or city crossings. To pave the way for autonomous road sweeping robots to operate in such difficult and complex environments, a benchmark suite with three large-scale 3D environments representative of this task is presented. On this benchmark we evaluate a new Coverage Path Planning method in comparison with previous well performing algorithms, and demonstrate state-of-the-art performance of the proposed method. Part of the success, for all evaluated algorithms, is the usage of automated domain adaptation by in-the-loop parameter optimization using Bayesian Optimization. Apart from improving the performance, tedious and bias-prone manual tuning is made obsolete, which makes the evaluation more robust and the results even stronger.
|
|
| 7. |
- Hayes, Conor F., et al.
(författare)
-
A Brief Guide to Multi-Objective Reinforcement Learning and Planning
- 2023
-
Ingår i: Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS). - 9781450394321 ; , s. 1988-1990
-
Konferensbidrag (refereegranskat)abstract
- Real-world sequential decision-making tasks are usually complex, and require trade-offs between multiple–often conflicting–objectives. However, the majority of research in reinforcement learning (RL) and decision-theoretic planning assumes a single objective, or that multiple objectives can be handled via a predefined weighted sum over the objectives. Such approaches may oversimplify the underlying problem, and produce suboptimal results. This extended abstract outlines the limitations of using a semi-blind iterative process to solve multi-objective decision making problems. Our extended paper [4], serves as a guide for the application of explicitly multi-objective methods to difficult problems.
|
|
| 8. |
- Hayes, Conor F., et al.
(författare)
-
A practical guide to multi-objective reinforcement learning and planning
- 2022
-
Ingår i: Autonomous Agents and Multi-Agent Systems. - New York, NY, United States : Springer. - 1387-2532 .- 1573-7454. ; 36:1
-
Tidskriftsartikel (refereegranskat)abstract
- Real-world sequential decision-making tasks are generally complex, requiring trade-offs between multiple, often conflicting, objectives. Despite this, the majority of research in reinforcement learning and decision-theoretic planning either assumes only a single objective, or that multiple objectives can be adequately handled via a simple linear combination. Such approaches may oversimplify the underlying problem and hence produce suboptimal results. This paper serves as a guide to the application of multi-objective methods to difficult problems, and is aimed at researchers who are already familiar with single-objective reinforcement learning and planning methods who wish to adopt a multi-objective perspective on their research, as well as practitioners who encounter multi-objective decision problems in practice. It identifies the factors that may influence the nature of the desired solution, and illustrates by example how these influence the design of multi-objective decision-making systems for complex problems.
|
|
| 9. |
- Heintz, Fredrik, 1975-
(författare)
-
Commentary on AI in the EU
- 2020
-
Ingår i: Human-centred AI in the EU. - : European Liberal Forum (ELF). - 9789187379819 ; , s. 1-12
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
| 10. |
- Kjällander, Susanne, et al.
(författare)
-
Signs of learning in middle school computing education
- 2022
-
Konferensbidrag (refereegranskat)abstract
- Programming has been part of Swedish elementary school curriculum for six years and the aim of this full paper is to find out how teachers can design programming activities so that students engage and learn. A mix-methods research project with a social semiotic, multimodal theoretical framework – Designs for learning – is used to investigate teaching and learning in a class during three years. The results in this small-scale study indicate that collaboration is a successful didactic design for programming lessons in school. Computational thinking is prevalent and both digital skills (such as coding) and digital competencies (such as understanding the impact of technology in society) are practiced and met in programming lessons merging Science, Technology, Engineering, Arts, and Mathematics.
|
|
