Umeå universitets logga

For natural and efficient verbal communication between a robot and humans, the robot should be able to learn names and appearances of new objects it encounters. In this paper we present a solution combining active sensing of images with text based and image based search on the Internet. The approach allows the robot to learn both object name and how to recognise similar objects in the future, all self-supervised without human assistance. One part of the solution is a novel iterative method to determine the object name using image classi- fication, acquisition of images from additional viewpoints, and Internet search. In this paper, the algorithmic part of the proposed solution is presented together with evaluations using manually acquired camera images, while Internet data was acquired through direct and reverse image search with Google, Bing, and Yandex. Classification with multi-classSVM and with five different features settings were evaluated. With five object classes, the best performing classifier used a combination of Pyramid of Histogram of Visual Words (PHOW) and Pyramid of Histogram of Oriented Gradient (PHOG) features, and reached a precision of 80% and a recall of 78%.

In verbal human-robot interaction natural language utterances have to be grounded in visual scenes by the robot. Visual language grounding is a challenging task that includes identifying a primary object among several objects, together with the object properties and spatial relations among the objects. In this paper we focus on extracting this information from sentences only. We propose two language modelling techniques, one uses regular expressions and the other one utilizes Euclidian distance. We compare these two proposed techniques with two other techniques that utilize tree structures, namely an extended Hobb’s algorithm and an algorithm that utilizes a Stanford parse tree. A comparative analysis between all language modelling techniques shows that our proposed two approaches require less computational time than the tree-based approaches. All approaches perform good identifying the primary object and its property, but for spatial relation extraction the Stanford parse tree algorithm performs better than the other language modelling techniques. Time elapsed for the Stanford parse tree algorithm is higher than for the other techniques.

In this paper, we claim that Lindenmayer systems (L systems) –more precisely, ET0L systems– can be considered as bio-inspired multi-agent systems that, because of its inherent features, can be usefully applied to the field of natural language processing (NLP). L systems are a biologically inspired branch of the field of formal languages that provide a parallel and non-sequential grammatical formalism and that can be expressed as a multi-agent system. Taking into account these features and the benefits of the multi-agent approach to NLP, we propose to apply L systems to the description, analysis and processing of natural languages.

In this paper, we investigate the linguistic relevance of Lindenmayer Systems (L Systems). L systems were introduced in the late sixties by Aristid Lindemayer as a mathematical theory of biological development. Thus they can be considered as one of the first bio-inspired models in the theory of formal languages. Two main properties in L systems are 1) the idea of parallelism in the rewriting process and 2) their expressiveness to describe non-context free structures that can be found in natural languages. Therefore, the linguistic relevance of this formalism is clearly based on three main features: bio-inspiration, parallelism and generation of non-context free languages. Despite these interesting properties, L systems have not been investigated from a linguistic point of view. With this paper we point out the interest of applying these bio-inspired systems to the description and processing of natural language.

The Umeå Student Conference in Computing Science (USCCS) is organized annually as part of a course given by the Computing Science department at Umeå University. The objective of the course is to give the students a practical introduction to independent research, scientific writing, and oral presentation. A student who participates in the course first selects a topic and a research question that they are interested in. If the topic is accepted, the student outlines a paper and composes an annotated bibliography to give a survey of the research topic. The main work consists of conducting the actual research that answers the question asked, and convincingly and clearly reporting the results in a scientific paper. Another major part of the course is multiple internal peer review meetings in which groups of students read each others’ papers and give feedback to the author. This process gives valuable training in both giving and receiving criticism in a constructive manner. Altogether, the students learn to formulate and develop their own ideas in a scientific manner, in a process involving internal peer reviewing of each other’s work and under supervision of the teachers, and incremental development and refinement of a scientific paper. Each scientific paper is submitted to USCCS through an on-line submission system, and receives two reviews. Based on the review, the editors of the conference proceedings issue a decision of preliminary acceptance of the paper to each author. If, after final revision, a paper is accepted, the student is given the opportunity to present the work at the conference. The review process and the conference format aims at mimicking realistic settings for publishing and participation at scientific conferences.

The Umeå Student Conference in Computing Science (USCCS) is an annual event organized as part of a course offered by the Department of Computing Science at Ume ̊a University. The primary aim of the course is to provide students with a hands-on introduction to independent research, scientific writing, and oral presentation. 

A student who participates in the course selects a topic in computing science and related areas and formulates a research question. The course revolves around three significant milestones. The first milestone requires students to write a lit- erature overview with an annotated bibliography, demonstrating not only their academic proficiency but also grounding their research into existing literature - standing on the shoulder of giants. The second milestone involves the actual research and its description in a scholarly manner, demonstrating a commitment to academic excellence, rigour and adherence to high standards. The third milestone encompasses the analysis and discussion of the obtained results, ensuring a thorough and objective examination. 

These three milestones are supported by three peer-review group meetings, consisting of 4-5 students each. During these sessions, each ongoing draft or milestone is efficiently and critically discussed aiming at guidance and improvement of the draft. This process provides valuable training in both giving and receiving constructive criticism. 

In addition, four lectures support the students’ learning and progress in the incremental development and refinement of a scientific paper, and timely discusssions on research ethics and quality. 

Each scientific paper is submitted to USCCS through EasyChair, an on-line submission system, and receives anonymous reviews from experts in the field. Based on the reviews and the editor’s assessment a decision of acceptance is made. Reviewers’ comments are incorporated, and the revised manuscripts undergo a final review before being included in these proceedings. The review process and conference format aim to simulate realistic settings for publishing processes and participation in scientific conferences. 

The conference is the highlight of the course, and this year, we received 14 submissions out of a possible 16, each thoroughly reviewed by experts listed on the following page. As a result, 8 submissions have been accepted for presentation at the conference. We extend our gratitude to the reviewers for their efforts within a tight timeframe and busy schedules. 

We also thank all authors for their dedication and outstanding final results, which will be presented during the conference. We wish all participants interesting exchange of ideas and stimulating discussions throughout USCCS. 

Millstream systems have recently been proposed as a formalization of the linguistic idea that natural language should be described as a combination of different modules related by interfaces. In this paper we investigate algorithmic properties of Millstream systems having regular tree grammars as modules and MSO logic as interface logic. We focus on the so-called completion problem: Given trees generated by a subset of the modules, can they be completed into a valid configuration of the Millstream system?

We introduce and investigate stack transducers, which are one-way stack automata with an output tape. A one-way stack automaton is a classical pushdown automaton with the additional ability to move the stack head inside the stack without altering the contents. For stack transducers, we distinguish between a digging and a non-digging mode. In digging mode, the stack transducer can write on the output tape when its stack head is inside the stack, whereas in non-digging mode, the stack transducer is only allowed to emit symbols when its stack head is at the top of the stack. These stack transducers have a motivation from natural-language interface applications, as they capture long-distance dependencies in syntactic, semantic, and discourse structures. We study the computational capacity for deterministic digging and non-digging stack transducers, as well as for their non-erasing and checking versions. We finally show that even for the strongest variant of stack transducers the stack languages are regular.

We introduce and investigate stack transducers, which are one-way stack automata with an output tape. A one-way stack automaton is a classical pushdown automaton with the additional ability to move the stack head inside the stack without altering the contents. For stack transducers, we distinguish between a digging and a non-digging mode. In digging mode, the stack transducer can write on the output tape when its stack head is inside the stack, whereas in non-digging mode, the stack transducer is only allowed to emit symbols when its stack head is at the top of the stack. These stack transducers have a motivation from natural language interface applications, as they capture long-distance dependencies in syntactic, semantic, and discourse structures.We study the computational capacity for deterministic digging and non-digging stack transducers, as well as for their non-erasing and checking versions. We finally show that even for the strongest variant of stack transducers the stack languages are regular.

This special issue is dedicated to Professor Helmut Jürgensen on the occasion of his 75th birthday and in appreciation of his scientific work and his impact as teacher, mentor, and person. The sixteen papers in this special issue were submitted by invitation of the guest editors. Each paper was reviewed by at least two referees. The authors of the papers in this special issue are collaborators, co-authors, or scientific descendents of Helmut Jürgensen.

We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular-interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any determinstic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.

In this short paper we discuss how incorporatingsocial practices in robotics may contribute to how well humansunderstand robots’ actions and intentions. Since social practicestypically are applied by all interacting parties, also the robots’understanding of the humans may improve.We further discuss how the involved mechanisms have to beadjusted to fit the cultural context in which the interaction takesplace, and how social practices may have to be transformed tofit a robot’s capabilities and limitations.

We introduce Millstream systems, a mathematical framework in the tradition of the Theory of Computation that uses logic to formalize the interfaces between different aspects of language, the latter being described by any number of independent modules. Unlike other approaches that serve a similar goal, Millstream systems neither presuppose nor establish a particular linguistic theory or focus, but can be instantiated in various ways to accomodate different points of view.

Millstream systems have been proposed as a non-hierarchical method for modelling natural language. Millstream congurations represent and connect multiple structural aspects of sentences. We present a method by which the Millstream congurations corresponding to a sentence are constructed. The construction is incremental, that is, it proceeds as the sentence is being read and is complete when the end of the sentence is reached. It is based on graph transformations and a lexicon which associates words with rules for the graph transformations.

Millstream systems have been proposed as a non-hierarchical method for modelling natural language. Millstream configurations represent and connect multiple structural aspects of sentences. We present a method by which the Millstream configurations corresponding to a sentence are constructed. The construction is incremental, that is, it proceeds as the sentence is being read and is complete when the end of the sentence is reached. It is based on graph transformations and a lexicon which associates words with graph transformation rules that implement the incremental construction process.

We investigate interaction patterns for humans interacting with explainable and non-explainable robots. Non-explainable robots are here robots that do not explain their actions or non-actions, neither do they give any other feedbackduring interaction, in contrast to explainable robots. We video recorded and analyzed human behavior during a board game, where 20 humans verbally instructed either an explainable or non-explainable Pepper robot to move objects on the board. The transcriptions and annotations of the videos were transformed into transactions for association rule mining. Association rules discovered communication patterns in the interaction between the robots and the humans, and the most interesting rules were also tested with regular chi-square tests. Some statistically significant results are that there is a strong correlation between men and non-explainable robots and women and explainable robots, and that humans mirror some of the robot’s modality. Our results also show that it is important to contextualize human interaction patterns, and that this can be easily done using association rules as an investigative tool. The presented results are important when designing robots that should adapt their behavior to become understandable for the interacting humans.

In this paper we model dynamic group formation and resource allocation with grammars in order to gain a deeper understanding into the involved processes. Modelling with grammars allows us to describe resource allocation and group formation as generative processes that provide, at any given time, information about at what stage the process of group formation and resource allocation is. We divide our model into four phases: (1) resource supply, (2) candidate group formation, (3) final group formation, and (4) resource distribution. In particular, we show that we can use permitting random context grammars to describe the first two phases. For the third phase we introduce an algorithm that determines based on a resource allocation strategy the final group to which resources are distributed. The last phase is described with random context grammars under a specific leftmost derivation mode. Our model shows that if information about the available resource and candidate group formation is distributed and kept separate, then the synchronisation of this information at a later stage (i.e. resource distribution phase) needs a more powerful grammar model.

In this paper we model virtual buying cooperatives (VBC) with grammars of regulated rewriting and show that, if VBC relevant information is distributed over several successive VBC processes and must, in a later stage, be synchronised and co-ordinated, the formal grammar needs to be very powerful with respect to mode of derivation and thus generative capacity. In particular, we show how to model the supplier phase, invitation phase, and declaration phase of a VBC with random permitting context grammars and the VBC reservation phase with random context grammars under a special kind of leftmost derivation. If we use random permitting context grammars for all processes, we can only model a VBC formation during which information is introduced and processed locally and successively rather than being spread over different VBC processes.

An overlooked problem in Learning From Demonstration is the ambiguity that arises, for instance, when the robot is equipped with more sensors than necessary for a certain task. Simply trying to repeat all aspects of a demonstration is seldom what the human teacher wants, and without additional information, it is hard for the robot to know which features are relevant and which should be ignored. This means that a single demonstration maps to several different behaviours the teacher might have intended. This one-to-many (or many-to-many) mapping from a demonstration (or several demonstrations) into possible intended behaviours is the ambiguity that is the topic of this paper. Ambiguity is defined as the size of the current hypothesis space. We investigate the nature of the ambiguity for different kinds of hypothesis spaces and how it is reduced by a new concept learning algorithm.

The Umeå Student Conference in Computing Science (USCCS) is organized annually as part of a course given by the Computing Science department at Umeå University. The objective of the course is to give the students a practical introduction to independent research, scientific writing, and oral presentation.

A student who participates in the course first selects a topic and a research question that he or she is interested in. If the topic is accepted, the student outlines a paper and composes an annotated bibliography to give a survey of the research topic. The main work consists of conducting the actual research that answers the question asked, and convincingly and clearly reporting the results in a scientific paper. Another major part of the course is multiple internal peer review meetings in which groups of students read each others’ papers and give feedback to the author. This process gives valuable training in both giving and receiving criticism in a constructive manner. Altogether, the students learn to formulate and develop their own ideas in a scientific manner, in a process involving internal peer reviewing of each other’s work and under supervision of the teachers, and incremental development and refinement of a scientific paper.

Each scientific paper is submitted to USCCS through an on-line submission system, and receives reviews written by members of the Computing Science department. Based on the review, the editors of the conference proceedings (the teachers of the course) issue a decision of preliminary acceptance of the paper to each author. If, after final revision, a paper is accepted, the student is given the opportunity to present the work at the conference. The review process and the conference format aims at mimicking realistic settings for publishing and participation at scientific conferences.

This paper describes ongoing and planned work on incremental language processing coupled to inference of expected robot actions. Utterances are processed word-by-word, simultaneously with inference of expected robot actions, thus enabling the robot to prepare and act proactively to human utterances. We believe that such a model results in more natural human-robot communication since proactive behavior is a feature of human-human communication.

The degree of nondeterminism is a measure of syntactic complexity which was investigated for parallel and sequential rewriting systems. In this paper, we consider the degree of nondeterminsm for tree adjoining grammars and their languages and head grammars and their languages. We show that a degree of nondeterminism of 2 suffices for both formalisms in order to generate all languages in their respective language families. Furthermore, we show that deterministic tree adjoining grammars (those with degree of nondeterminism equal to 1), can generate non-context-free languages, in contrast to deterministic head grammars which can only generate languages containing a single word. 

We introduce and investigate input-driven stack automata, which are a generalization of input-driven pushdown automata that recently became popular under the name visibly pushdown automata. Basically, the idea is that the input letters uniquely determine the operations on the pushdown store. This can nicely be generalized to stack automata by further types of input letters which are responsible for moving the stack pointer up or down. While visibly pushdown languages share many desirable properties with regular languages, input-driven stack automata languages do not necessarily so. We prove that deterministic and non- deterministic input-driven stack automata have different computational power, which shows in passing that one cannot construct a deterministic input-driven stack automaton from a nondeterministic one. We study the computational capacity of these devices. Moreover, it is shown that the membership problem for nondeterministic input-driven stack automata languages is NP-complete.

In many complex robotics systems, interaction takes place in all directions between human, robot, and environment. Performance of such a system depends on this interaction, and a proper evaluation of a system must build on a proper modeling of interaction, a relevant set of performance metrics, and a methodology to combine metrics into a single performance value. In this paper, existing models of human-robot interaction are adapted to fit complex scenarios with one or several humans and robots. The interaction and the evaluation process is formalized, and a general method to fuse performance values over time and for several performance metrics is presented. The resulting value, denoted interaction quality, adds a dimension to ordinary performance metrics by being explicit about the interplay between performance metrics, and thereby provides a formal framework to understand, model, and address complex aspects of evaluation of human-robot interaction. 

We study the fixed membership problem for k-uniformly-limited and propagating ET0L systems (kulEPT0L systems). To this end, the algorithm given in [7] is applied. It follows that kulEPT0L languages are parsable in polynomial time. Since kulEPT0L languages are semi-linear [1] and kulEPT0L systems generate certain non-context-free languages, which capture the non-context-free phenomena occurring in natural languages, this is the last building block to show that kulEPT0L languages, for k ≥ 2, belong to the family of mildly context-sensitive languages.

One important aspect when designing understandable robots is how robots should communicate with a human user to be understood in the best way. In elder care applications this is particularly important, and also difficult since many older adults suffer from various kinds of impairments. In this paper we present a solution where communication modality and communication parameters are adapted to fit both a user profile and an environment model comprising information about light and sound conditions that may affect communication. The Rasa dialogue manager is complemented with necessary functionality, and the operation is verified with a Pepper robot interacting with several personas with impaired vision, hearing, and cognition. Several relevant ethical questions are identified and briefly discussed, as a contribution to the WARN workshop.

In human communication, backchanneling is an important part of the natural interaction protocol. The purpose is to signify the listener’s attention, understanding, agreement, or to indicate that a speaker should go on talking. While the effects of backchanneling robots on humans have been investigated, studies of how and when humans backchannel to talking robots is poorly studied. In this paper we investigate how the robot’s behavior as a speaker affects a human listener’s backchanneling behavior. This is interesting in Human-Robot Interaction since backchanneling between humans has been shown to support more fluid interactions, and human-robot interaction would therefore benefit from mimicking this human communication feature. The results show that backchanneling increases when the robot exhibits backchannel-inviting cues such as pauses and gestures. Furthermore, clear differences between how a human backchannels to another human and to a robot are shown.

In human communication, backchanneling is an important part of the natural interaction protocol. The purpose is to signify the listener's attention, understanding, agreement, or to indicate that a speaker should go on talking. While the effects of backchanneling robots on humans have been investigated, studies of how and when humans backchannel to talking robots is poorly studied. In this paper we investigate how the robot's behavior as a speaker affects a human listener's backchanneling behavior. This is interesting in Human -Robot Interaction since backchanneling between humans has been shown to support more fluid interactions, and human -robot interaction would therefore benefit from mimicking this human communication feature. The results show that backchanneling increases when the robot exhibits backchannel-inviting cues such as pauses and gestures. Furthermore, clear differences between how a human backchannels to another human and to a robot are shown.

Semantic embeddings have advanced the state of the art for countless natural language processing tasks, and various extensions to multimodal domains, such as visual-semantic embeddings, have been proposed. While the power of visual-semantic embeddings comes from the distillation and enrichment of information through machine learning, their inner workings are poorly understood and there is a shortage of analysis tools. To address this problem, we generalize the notion of probing tasks to the visual-semantic case. To this end, we (i) discuss the formalization of probing tasks for embeddings of image-caption pairs, (ii) define three concrete probing tasks within our general framework, (iii) train classifiers to probe for those properties, and (iv) compare various state-of-the-art embeddings under the lens of the proposed probing tasks. Our experiments reveal an up to 12% increase in accuracy on visual-semantic embeddings compared to the corresponding unimodal embeddings, which suggest that the text and image dimensions represented in the former do complement each other

As robots become more and more capable and autonomous, there is an increased need for humans to understand what the robots do and think. In this paper we investigate what such understanding means and includes, and how robots are and can be designed to support understanding. We present a model of interaction for understanding. The aim is to provide a uniform formal understanding of the large body of existing work, and also to support continued work in the area.

As robots become more and more capable and autonomous, there is an increasing need for humans to understand what the robots do and think. In this paper, we investigate what such understanding means and in- cludes, and how robots can be designed to support un- derstanding. After an in-depth survey of related earlier work, we discuss examples showing that understanding includes not only the intentions of the robot, but also de- sires, knowledge, beliefs, emotions, perceptions, capabil- ities, and limitations of the robot. The term understandingis formally defined, and the term communicative actions is defined to denote the various ways in which a robot may support a human’s understanding of the robot. A novel model of interaction for understanding is presented. The model describes how both human and robot may utilize a first or higher-order theory of mind to understand each other and perform communicative actions in order to sup- port the other’s understanding. It also describes simpler cases in which the robot performs static communicative actions in order to support the human’s understanding of the robot. In general, communicative actions performed by the robot aim at reducing the mismatch between the mind of the robot, and the robot’s inferred model of the human’s model of the mind of the robot. Based on the pro- posed model, a set of questions are formulated, to serve as support when developing and implementing the model in real interacting robots.

In public media as well as in scientific publications, the term bias is used in conjunction with machine learning in many different contexts, and with many different meanings. This paper proposes a taxonomy of these different meanings, terminology, and definitions by surveying the, primarily scientific, literature on machine learning. In some cases, we suggest extensions and modifications to promote a clear terminology and completeness. The survey is followed by an analysis and discussion on how different types of biases are connected and depend on each other. We conclude that there is a complex relation between bias occurring in the machine learning pipeline that leads to a model, and the eventual bias of the model (which is typically related to social discrimination). The former bias may or may not influence the latter, in a sometimes bad, and sometime good way.