In this seminar, we will study different approaches to model and to specify agent behaviour. We will look at theoretical foundations as well as practical implementations. Topics range from multi-agent collaboration models over belief management and modelling uncertainty to human-robot interaction models.
Participation
Students of Master programs can participate in this seminar. For Master Informatik students, the seminar belongs to the fields Data and Information Management. Certain topics may also be suitable for the field Theoretical Computer Science, please contact us beforehand. For Master Software Systems Engineering (SSE) students, it belongs to the field Data and Information Management. As above, some topics may qualify for the area Theoretical Foundations of SSE, contact us beforehand.
Places are allocated centrally. In your application please clearly indicate your prior knowledge of the subject (see the requirements section). We won’t be able to consider your application otherwise. The number of available slots is limited.
Requirements
Knowledge of the fundamental concepts of Artificial Intelligence is strongly recommended, an understanding of knowledge representation and logic will be helpful. Relevant courses include Introduction into Artificial Intelligence, Knowledge Representation, and Mathematical Logic.
Topics
Learning of Behavior Trees for Autonomous Agents
M. Colledanchise, R. Nattanmai Parasuraman and P. Ogren, “Learning of Behavior Trees for Autonomous Agents,” in IEEE Transactions on Games. doi: 10.1109/TG.2018.2816806
Abstract:
In this paper, we study the problem of automatically synthesizing a successful Behavior Tree (BT) in an a-priori unknown dynamic environment. Starting with a given set of behaviors, a reward function, and sensing in terms of a set of binary conditions, the proposed algorithm incrementally learns a switching structure in terms of a BT, that is able to handle the situations encountered. Exploiting the fact that BTs generalize And-Or-Trees and also provide very natural chromosome mappings for genetic pro- gramming, we combine the long term performance of Genetic Programming with a greedy element and use the And-Or analogy to limit the size of the resulting structure. Finally, earlier results on BTs enable us to provide certain safety guarantees for the resulting system. Using the testing environment Mario AI we compare our approach to alternative methods for learning BTs and Finite State Machines. The evaluation shows that the proposed approach generated solutions with better performance, and often fewer nodes than the other two methods.
keywords: Artificial intelligence;Planning;Stochastic processes;Games;Heuristic algorithms;Genetics;Safety,
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8319483&isnumber=8116623
Detection of Plan Deviation in Multi-Agent Systems
Bikramjit Banerjee, Steven Loscalzo, Daniel Lucas Thompson
Abstract:
Plan monitoring in a collaborative multi-agent system requires an agent to not only monitor the execution of its own plan, but also to detect possible deviations or failures in the plan execution of its teammates. In domains featuring partial observability and uncertainty in the agents’ sensing and actuation, especially where communication among agents is sparse (as a part of a cost-minimized plan), plan monitoring can be a significant challenge. We design an Expectation Maximization (EM) based algorithm for detection of plan deviation of teammates in such a multi-agent system. However, a direct implementation of this algorithm is intractable, so we also design an alternative approach grounded on the agents’ plans, for tractability. We establish its equivalence to the intractable version, and evaluate these techniques in some challenging tasks.
URL: https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/viewPaper/12429
The Advantages of Using Behavior Trees in Mult-Robot Systems
M. Colledanchise, A. Marzinotto, D. V. Dimarogonas and P. Oegren, “The Advantages of Using Behavior Trees in Mult-Robot Systems,” Proceedings of ISR 2016: 47st International Symposium on Robotics, Munich, Germany, 2016, pp. 1-8.
Abstract:
Multi-robot teams offer possibilities of improved performance and fault tolerance, compared to single robot solutions. In this paper, we show how to realize those possibilities when starting from a single robot system controlled by a Behavior Tree (BT). By extending the single robot BT to a multi-robot BT, we are able to combine the fault tolerant properties of the BT, in terms of built-in fallbacks, with the fault tolerance inherent in multi-robot approaches, in terms of a faulty robot being replaced by another one. Furthermore, we improve performance by identifying and taking advantage of the opportunities of parallel task execution, that are present in the single robot BT. Analyzing the proposed approach, we present results regarding how mission performance is affected by minor faults (a robot losing one capability) as well as major faults (a robot losing all its capabilities).
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7558452&isnumber=7558448
Multi-Agent Plan Recognition: Formalization and Algorithms
Bikramjit Banerjee, Landon Kraemer, Jeremy Lyle
Abstract:
Multi-Agent Plan Recognition (MAPR) seeks to identify the dynamic team structures and team behaviors from the observations of the activity-sequences of a set of intelligent agents, based on a library of known team-activities (plan library). It has important applications in analyzing data from automated monitoring, surveillance, and intelligence analysis in general. In this paper, we formalize MAPR using a basic model that explicates the cost of abduction in single agent plan recognition by “flattening” or decompressing the (usually compact, hierarchical) plan library. We show that single-agent plan recognition with a decompressed library can be solved in time polynomial in the input size, while it is known that with a compressed (by partial ordering constraints) library it is NP-complete. This leads to an important insight: that although the compactness of the plan library plays an important role in the hardness of single-agent plan recognition (as recognized in the existing literature), that is not the case with multiple agents. We show, for the first time, that MAPR is NP-complete even when the (multi-agent) plan library is fully decompressed. As with previous solution approaches, we break the problem into two stages: hypothesis generation and hypothesis search. We show that Knuth’s Algorithm X'' (with the efficient dancing links’’ representation) is particularly suited for our model, and can be adapted to perform a branch and bound search for the second stage, in this model. We show empirically that this new approach leads to significant pruning of the hypothesis space in MAPR.
Keywords: multi-agent plan recognition, multi-agent teams, multi-agent systems, plan recognition
URL: https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewPaper/1838
Toward Open Knowledge Enabling for Human-Robot Interaction
Chen, Xiaoping and Xie, Jiongkun and Ji, Jianmin and Sui, Zhiqiang
Abstract:
This paper presents an effort to enable robots to utilize open-source knowledge resources autonomously for human-robot interaction. The main challenges include how to extract knowledge in semi-structured and unstructured natural languages, how to make use of multiple types of knowledge in decision making, and how to identify the knowledge that is missing. A set of techniques for multi-mode natural language processing, integrated decision making, and open knowledge searching is proposed. The OK-KeJia robot prototype is implemented and evaluated, with special attention to two tests on 11,615 user tasks and 467 user desires. The experiments show that the overall performance improves remarkably due to the use of appropriate open knowledge.
Keywords: NLP, decision making, human-robot interaction, open knowledge, social robotics
URL: https://dl.acm.org/citation.cfm?id=3109694
Performance analysis of stochastic behavior trees
M. Colledanchise, A. Marzinotto and P. Ögren, “Performance analysis of stochastic behavior trees,” 2014 IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, 2014, pp. 3265-3272. doi: 10.1109/ICRA.2014.6907328
Abstract:
This paper presents a mathematical framework for performance analysis of Behavior Trees (BTs). BTs are a recent alternative to Finite State Machines (FSMs), for doing modular task switching in robot control architectures. By encoding the switching logic in a tree structure, instead of distributing it in the states of a FSM, modularity and reusability are improved. In this paper, we compute performance measures, such as success/failure probabilities and execution times, for plans encoded and executed by BTs. To do this, we first introduce Stochastic Behavior Trees (SBT), where we assume that the probabilistic performance measures of the basic action controllers are given. We then show how Discrete Time Markov Chains (DTMC) can be used to aggregate these measures from one level of the tree to the next. The recursive structure of the tree then enables us to step by step propagate such estimates from the leaves (basic action controllers) to the root (complete task execution). Finally, we verify our analytical results using massive Monte Carlo simulations, and provide an illustrative example of the results for a complex robotic task.
keywords: discrete time systems;finite state machines;Markov processes;robots;trees (mathematics);stochastic behavior trees;performance analysis;finite state machines;FSM;modular task switching;robot control architectures;switching logic;tree structure;performance measures;success-failure probabilities;SBT;discrete time Markov chains;DTMC;Monte Carlo simulations;complex robotic task;Markov processes;Robots;Probabilistic logic;Transient analysis;Switches;Vectors;Reliability,
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6907328&isnumber=6906581
ALLEGRO: Belief-Based Programming in Stochastic Dynamical Domains
Vaishak Belle, Hector Levesque
Abstract:
High-level programming languages are an influential control paradigm for building agents that are purposeful in an incompletely known world. GOLOG, for example, allows us to write programs, with loops, whose constructs refer to an explicit world model axiomatized in the expressive language of the situation calculus. Over the years, GOLOG has been extended to deal with many other features, the claim being that these would be useful in robotic applications. Unfortunately, when robots are actually deployed, effectors and sensors are noisy, typically characterized over continuous probability distributions, none of which is supported in GOLOG, its dialects or its cousins. This paper presents ALLEGRO, a belief-based programming language for stochastic domains, that refashions GOLOG to allow for discrete and continuous initial uncertainty and noise. It is fully implemented and experiments demonstrate that ALLEGRO could be the basis for bridging high-level programming and probabilistic robotics technologies in a general way.
URL: https://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/viewPaper/11431
Additional information
Introductory Meeting
- The introductory meeting will take place in the beginning of the semester, the exact date will be announced. Participation is compulsory.
Seminar Procedure
- Besides writing your own term paper, you are asked to review other students’ term papers. We will use a conference management system (e.g., EasyChair) for this procedure. It will involve strict deadlines. Meeting these deadlines is mandatory. At the end of the seminar each student needs to give a talk on his topic in front of the other students and members of our group. Attendance of these talks and participation in the discussions is mandatory.
Seminar Date
- The seminar will be held as a block seminar on two or three days, likely during the semester break.
Typesetting
- You may use this LaTeX template for your term paper.
General Info
- Please read and understand our general information and suggestions on seminars!
- The introductory slides contain information about the schedule and requirements.
Library Tour
- The Computer Science Library offers guided tours on how to find literature in the library and how to prepare a seminar. Interested students should enlist for a tour in the preliminary discussion.