1. |
- Präntare, Fredrik, 1990-, et al.
(author)
-
An Algorithm for Simultaneous Coalition Structure Generation and Task Assignment
- 2017
-
In: PRIMA 2017: Principles and Practice of Multi-Agent Systems 20th International Conference, Nice, France, October 30 – November 3, 2017, Proceedings. - Cham : Springer. - 9783319691305 - 9783319691312 ; , s. 514-522
-
Conference paper (peer-reviewed)abstract
- Groups of agents in multi-agent systems may have to cooperate to solve tasks efficiently, and coordinating such groups is an important problem in the field of artificial intelligence. In this paper, we consider the problem of forming disjoint coalitions and assigning them to independent tasks simultaneously, and present an anytime algorithm that efficiently solves the simultaneous coalition structure generation and task assignment problem. This NP-complete combinatorial optimization problem has many real-world applications, including forming cross-functional teams aimed at solving tasks. To evaluate the algorithm's performance, we extend established methods for synthetic problem set generation, and benchmark the algorithm using randomized data sets of varying distribution and complexity. Our results show that the presented algorithm efficiently finds optimal solutions, and generates high quality solutions when interrupted prior to finishing an exhaustive search. Additionally, we apply the algorithm to solve the problem of assigning agents to regions in a commercial computer-based strategy game, and empirically show that our algorithm can significantly improve the coordination and computational efficiency of agents in a real-time multi-agent system.
|
|
2. |
- Präntare, Fredrik, 1990-, et al.
(author)
-
An Anytime Algorithm for Simultaneous Coalition Structure Generation and Assignment
- 2018
-
In: PRIMA 2018: Principles and Practice of Multi-Agent Systems. - Cham : Springer International Publishing. - 9783030030971 - 9783030030988 ; , s. 158-174
-
Conference paper (peer-reviewed)abstract
- A fundamental problem in artificial intelligence is how to organize and coordinate agents to improve their performance and skills. In this paper, we consider simultaneously generating coalitions of agents and assigning the coalitions to independent tasks, and present an anytime algorithm for the simultaneous coalition structure generation and assignment problem. This optimization problem has many real-world applications, including forming goal-oriented teams of agents. To evaluate the algorithm’s performance, we extend established methods for synthetic problem set generation, and benchmark the algorithm against CPLEX using randomized data sets of varying distribution and complexity. We also apply the algorithm to solve the problem of assigning agents to regions in a major commercial strategy game, and show that the algorithm can be utilized in game-playing to coordinate smaller sets of agents in real-time.
|
|
3. |
- Andersson, Olov, 1979-, et al.
(author)
-
Model-Based Reinforcement Learning in Continuous Environments Using Real-Time Constrained Optimization
- 2015
-
In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI). - : AAAI Press. - 9781577356981 ; , s. 2497-2503
-
Conference paper (peer-reviewed)abstract
- Reinforcement learning for robot control tasks in continuous environments is a challenging problem due to the dimensionality of the state and action spaces, time and resource costs for learning with a real robot as well as constraints imposed for its safe operation. In this paper we propose a model-based reinforcement learning approach for continuous environments with constraints. The approach combines model-based reinforcement learning with recent advances in approximate optimal control. This results in a bounded-rationality agent that makes decisions in real-time by efficiently solving a sequence of constrained optimization problems on learned sparse Gaussian process models. Such a combination has several advantages. No high-dimensional policy needs to be computed or stored while the learning problem often reduces to a set of lower-dimensional models of the dynamics. In addition, hard constraints can easily be included and objectives can also be changed in real-time to allow for multiple or dynamic tasks. The efficacy of the approach is demonstrated on both an extended cart pole domain and a challenging quadcopter navigation task using real data.
|
|
4. |
- Andersson, Olov, 1979-, et al.
(author)
-
Receding-Horizon Lattice-based Motion Planning with Dynamic Obstacle Avoidance
- 2018
-
In: 2018 IEEE Conference on Decision and Control (CDC). - : Institute of Electrical and Electronics Engineers (IEEE). - 9781538613955 - 9781538613948 - 9781538613962 ; , s. 4467-4474
-
Conference paper (peer-reviewed)abstract
- A key requirement of autonomous vehicles is the capability to safely navigate in their environment. However, outside of controlled environments, safe navigation is a very difficult problem. In particular, the real-world often contains both complex 3D structure, and dynamic obstacles such as people or other vehicles. Dynamic obstacles are particularly challenging, as a principled solution requires planning trajectories with regard to both vehicle dynamics, and the motion of the obstacles. Additionally, the real-time requirements imposed by obstacle motion, coupled with real-world computational limitations, make classical optimality and completeness guarantees difficult to satisfy. We present a unified optimization-based motion planning and control solution, that can navigate in the presence of both static and dynamic obstacles. By combining optimal and receding-horizon control, with temporal multi-resolution lattices, we can precompute optimal motion primitives, and allow real-time planning of physically-feasible trajectories in complex environments with dynamic obstacles. We demonstrate the framework by solving difficult indoor 3D quadcopter navigation scenarios, where it is necessary to plan in time. Including waiting on, and taking detours around, the motions of other people and quadcopters.
|
|
5. |
- Bergström, David, 1994-, et al.
(author)
-
Bayesian optimization for selecting training and validation data for supervised machine learning
- 2019
-
In: 31st annual workshop of the Swedish Artificial Intelligence Society (SAIS 2019), Umeå, Sweden, June 18-19, 2019..
-
Conference paper (other academic/artistic)abstract
- Validation and verification of supervised machine learning models is becoming increasingly important as their complexity and range of applications grows. This paper describes an extension to Bayesian optimization which allows for selecting both training and validation data, in cases where data can be generated or calculated as a function of a spatial location.
|
|
6. |
- de Leng, Daniel, 1988-, et al.
(author)
-
Approximate Stream Reasoning with Metric Temporal Logic under Uncertainty
- 2019
-
In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI). - Palo Alto : AAAI Press. ; , s. 2760-2767
-
Conference paper (peer-reviewed)abstract
- Stream reasoning can be defined as incremental reasoning over incrementally-available information. The formula progression procedure for Metric Temporal Logic (MTL) makes use of syntactic formula rewritings to incrementally evaluate formulas against incrementally-available states. Progression however assumes complete state information, which can be problematic when not all state information is available or can be observed, such as in qualitative spatial reasoning tasks or in robotics applications. In those cases, there may be uncertainty as to which state out of a set of possible states represents the ‘true’ state. The main contribution of this paper is therefore an extension of the progression procedure that efficiently keeps track of all consistent hypotheses. The resulting procedure is flexible, allowing a trade-off between faster but approximate and slower but precise progression under uncertainty. The proposed approach is empirically evaluated by considering the time and space requirements, as well as the impact of permitting varying degrees of uncertainty.
|
|
7. |
- de Leng, Daniel, 1988-
(author)
-
Robust Stream Reasoning Under Uncertainty
- 2019
-
Doctoral thesis (other academic/artistic)abstract
- Vast amounts of data are continually being generated by a wide variety of data producers. This data ranges from quantitative sensor observations produced by robot systems to complex unstructured human-generated texts on social media. With data being so abundant, the ability to make sense of these streams of data through reasoning is of great importance. Reasoning over streams is particularly relevant for autonomous robotic systems that operate in physical environments. They commonly observe this environment through incremental observations, gradually refining information about their surroundings. This makes robust management of streaming data and their refinement an important problem.Many contemporary approaches to stream reasoning focus on the issue of querying data streams in order to generate higher-level information by relying on well-known database approaches. Other approaches apply logic-based reasoning techniques, which rarely consider the provenance of their symbolic interpretations. In this work, we integrate techniques for logic-based stream reasoning with the adaptive generation of the state streams needed to do the reasoning over. This combination deals with both the challenge of reasoning over uncertain streaming data and the problem of robustly managing streaming data and their refinement.The main contributions of this work are (1) a logic-based temporal reasoning technique based on path checking under uncertainty that combines temporal reasoning with qualitative spatial reasoning; (2) an adaptive reconfiguration procedure for generating and maintaining a data stream required to perform spatio-temporal stream reasoning over; and (3) integration of these two techniques into a stream reasoning framework. The proposed spatio-temporal stream reasoning technique is able to reason with intertemporal spatial relations by leveraging landmarks. Adaptive state stream generation allows the framework to adapt to situations in which the set of available streaming resources changes. Management of streaming resources is formalised in the DyKnow model, which introduces a configuration life-cycle to adaptively generate state streams. The DyKnow-ROS stream reasoning framework is a concrete realisation of this model that extends the Robot Operating System (ROS). DyKnow-ROS has been deployed on the SoftBank Robotics NAO platform to demonstrate the system's capabilities in a case study on run-time adaptive reconfiguration. The results show that the proposed system - by combining reasoning over and reasoning about streams - can robustly perform stream reasoning, even when the availability of streaming resources changes.
|
|
8. |
- de Leng, Daniel, 1988-
(author)
-
Spatio-Temporal Stream Reasoning with Adaptive State Stream Generation
- 2017
-
Licentiate thesis (other academic/artistic)abstract
- A lot of today's data is generated incrementally over time by a large variety of producers. This data ranges from quantitative sensor observations produced by robot systems to complex unstructured human-generated texts on social media. With data being so abundant, making sense of these streams of data through reasoning is challenging. Reasoning over streams is particularly relevant for autonomous robotic systems that operate in a physical environment. They commonly observe this environment through incremental observations, gradually refining information about their surroundings. This makes robust management of streaming data and its refinement an important problem.Many contemporary approaches to stream reasoning focus on the issue of querying data streams in order to generate higher-level information by relying on well-known database approaches. Other approaches apply logic-based reasoning techniques, which rarely consider the provenance of their symbolic interpretations. In this thesis, we integrate techniques for logic-based spatio-temporal stream reasoning with the adaptive generation of the state streams needed to do the reasoning over. This combination deals with both the challenge of reasoning over streaming data and the problem of robustly managing streaming data and its refinement.The main contributions of this thesis are (1) a logic-based spatio-temporal reasoning technique that combines temporal reasoning with qualitative spatial reasoning; (2) an adaptive reconfiguration procedure for generating and maintaining a data stream required to perform spatio-temporal stream reasoning over; and (3) integration of these two techniques into a stream reasoning framework. The proposed spatio-temporal stream reasoning technique is able to reason with intertemporal spatial relations by leveraging landmarks. Adaptive state stream generation allows the framework to adapt in situations in which the set of available streaming resources changes. Management of streaming resources is formalised in the DyKnow model, which introduces a configuration life-cycle to adaptively generate state streams. The DyKnow-ROS stream reasoning framework is a concrete realisation of this model that extends the Robot Operating System (ROS). DyKnow-ROS has been deployed on the SoftBank Robotics NAO platform to demonstrate the system's capabilities in the context of a case study on run-time adaptive reconfiguration. The results show that the proposed system – by combining reasoning over and reasoning about streams – can robustly perform spatio-temporal stream reasoning, even when the availability of streaming resources changes.
|
|
9. |
- Färnqvist, Tommy, 1976-, et al.
(author)
-
Supporting Active Learning by Introducing an Interactive Teaching Tool in a Data Structures and Algorithms Course
- 2016
-
In: Proceedings of the 47th ACM Technical Symposium on Computer Science Education (SIGCSE 2016). - New York, NY, USA : ACM Publications. - 9781450336857 ; , s. 663-668
-
Conference paper (peer-reviewed)abstract
- Traditionally, theoretical foundations in data structures and algorithms (DSA) courses have been covered through lectures followed by tutorials, where students practise their understanding on pen-and-paper tasks. In this paper, we present findings from a pilot study on using the interactive e-book OpenDSA as the main material in a DSA course. The goal was to redesign an already existing course by building on active learning and continuous examination through the use of OpenDSA. In addition to presenting the study setting, we describe findings from four data sources: final exam, OpenDSA log data, pre and post questionnaires as well as an observation study. The results indicate that students performed better on the exam than during previous years. Students preferred OpenDSA over traditional textbooks and worked actively with the material, although a large proportion of them put off the work until the due date approaches.
|
|
10. |
- Färnqvist, Tommy, 1976-, et al.
(author)
-
Supporting Active Learning Using an Interactive Teaching Tool in a Data Structures and Algorithms Course
- 2015
-
In: Proceedings of 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng). ; , s. 76-79
-
Conference paper (other academic/artistic)abstract
- Traditionally, theoretical foundations in data structuresand algorithms (DSA) courses have been covered throughlectures followed by tutorials, where students practise theirunderstanding on pen-and-paper tasks. In this paper, we presentfindings from a pilot study on using the interactive e-bookOpenDSA as the main material in a DSA course. The goal was toredesign an already existing course by building on active learningand continuous examination through the use of OpenDSA. Inaddition to presenting the study setting, we describe findings fromfour data sources: final exam, OpenDSA log data, pre- and postcourse questionnaires as well as an observation study. The resultsindicate that students performed better on the exam than duringprevious years. Students preferred OpenDSA over traditionaltextbooks and worked actively with the material, although alarge proportion of them put off the work until the due dateapproaches.
|
|