Ebook: Eleventh Scandinavian Conference on Artificial Intelligence

The eleventh Scandinavian Conference on Artificial Intelligence is held in Trondheim, Norway, from the 24th to the 26th of May, 2011.

The conference is organised by NTNU, the Norwegian University of Science and Technology, together with NAIS, the Norwegian Artificial Intelligence Society. This year's program consists of three invited speakers, two tutorials and a three day conference. Less than half of the papers submitted to the conference were accepted for oral presentation; an additional 20% of the submissions were accepted as “short papers”, which also included a poster presentation.

This year's contributions cover a broad range of topics, from machine learning and planning, via robotics and cognition to applications of AI.

We are honoured to present invited speakers Michael Wooldridge, who talks about playing games with games; Ashwin Ram, talking about user-generated AI for interactive digital entertainment and Peter Nordin who talks about perspectives on AI in a business environment. We are also grateful for the tutorials by Finn V. Jensen and Thomas Ågotnes.

The editors of this volume would like to thank the members of the program committee for their competent assessment of the papers contributed. The members ensured that most contributions were reviewed by at least three competent referees.

We acknowledge the generous support of our industry sponsor Verdande Technologies and also the Norwegian research council and NTNU.

Trondheim, May 2011

Anders Kofod-Petersen, Fredrik Heintz, Helge Langseth

The past decade has been witness to a huge explosion of interest in the computational aspects of game theory. One topic that has received much attention is that of mechanism design. Crudely, mechanism design can be understood as the problem of designing games so that, if every player in the game acts rationally, certain desirable outcomes will result. In mechanism design, it is usually assumed that the designer of the mechanism has complete freedom to design a mechanism as desired. But this is not the reality of most real-world mechanism design problems: when a Government develops a new law, for example, they do not usually have a blank slate, but must work start from the framework of society as it exists. In this talk, I will present work we have done on the computational aspects of such “mechanism design for legacy systems”. In the settings we consider, a principal external to a system must try to engineer a mechanism to influence the system so that certain desirable outcomes will result from the rational action action of agents within the system. We consider two ways in which a principal might influence a system: First, through communication, which can be used to modify the beliefs of system participants, upon which players will choose actions to perform; and second, by imposing taxation schemes upon the system, so that the preferences of participants are perturbed appropriately.

User-generated content is everywhere: photos, videos, news, blogs, art, music, and every other type of digital media on the Social Web. Games are no exception. From strategy games to immersive virtual worlds, game players are increasingly engaged in creating and sharing nearly all aspects of the gaming experience: maps, quests, artifacts, avatars, clothing, even games themselves. Yet, there is one aspect of computer games that is not created and shared by game players: the AI. Building sophisticated personalities, behaviors, and strategies requires expertise in both AI and programming, and remains outside the purview of the end user.

To understand why authoring Game AI is hard, we need to understand how it works. AI can take digital entertainment beyond scripted interactions into the arena of truly interactive systems that are responsive, adaptive, and intelligent. I will discuss examples of AI techniques for character-level AI (in embedded NPCs, for example) and game-level AI (in the drama manager, for example). These types of AI enhance the player experience in different ways. The techniques are complicated and are usually implemented by expert game designers.

I propose an alternative approach to designing Game AI: Real-Time CBR. This approach extends CBR to real-time systems that operate asynchronously during game play, planning, adapting, and learning in an online manner. Originally developed for robotic control, Real-Time CBR can be used for interactive games ranging from multiplayer strategy games to interactive believable avatars in virtual worlds.

As with any CBR technique, Real-Time CBR integrates problem solving with learning. This property can be used to address the authoring problem. I will show the first Web 2.0 application that allows average users to create AIs and challenge their friends to play themÑwithout programming. I conclude with some thoughts about the future of AI-based Interactive Digital Entertainment.

This lecture will give three perspectives on artificial intelligence in a business environment: Some notes from a personal journey having created a dozen successful AI companies in Scandinavia. A collection of conclusions and observations hopefully valuable for anyone interested in turning their research into a commercial venture with a focus on how the Scandinavian market works. And finally an overview of the “lowest-hanging fruit” and biggest success stories of commercial AI at present.

The tutorial provides a survey on probabilistic decision graphs for modeling and solving decision problems under uncertainty. I shall give an introduction to influence diagrams, which is a popular framework for representing and solving sequential decision problems with a single decision maker. As the methods for solving influence diagrams can scale rather badly in the length of the decision sequence, I shall present a couple of approaches for calculating approximate solutions. The modeling scope of the influence diagram is limited to so-called symmetric decision problems. This limitation has motivated the development of alternative representation languages, which enlarge the class of decision problems that can be modeled efficiently. I shall present some of these alternative frameworks and demonstrate their expressibility using several examples.

Coordination is a central problem in multi-agent systems. Social laws (or normative systems) have emerged as a natural and powerful paradigm for coordinating multi-agent systems. The social laws paradigm exposes the whole spectrum between fully centralised and fully decentralised coordination mechanisms. A social law is, intuitively, a constraint on the behaviour of agents, which ensures that their individual behaviours are compatible. Typically, a social law is imposed off-line, minimising the chances of on-line conflict or the need to negotiate. The tutorial gives an overview of the state-of-the-art in research on the use of social laws for coordination. It discusses questions such as: how can a social law that ensures some particular global behaviour be automatically constructed? If two social laws achieve the same objective, which one should we use? How can we construct a social law that works even if some agents do not comply? Which agents are most important for a social law to achieve its objective? It turns out that to answer questions like these, we can apply a range of tools available from the interdisciplinary tool chest of multi-agent systems. The tutorial also gives instruction in research practices and methodology in multi-agent systems: what are key research questions of interest, and what are some of the most important methods employed in this interdisciplinary field? To answer the latter question, the tutorial exemplifies of how, e.g., formal logic, game theory, voting theory and complexity theory, can be used, and in particular how these frameworks can be combined.

This paper reviews methods for evaluating and analyzing the understandability of classification models in the context of data mining. The motivation for this study is the fact that the majority of previous work on evaluation and optimization of classification models has focused on assessing or increasing the accuracy of the models and thus user-oriented properties such as comprehensibility and understandability have been largely overlooked. We conduct a quantitative survey to examine the concept of understandability from the user's point of view. The survey results are analyzed using the analytic hierarchy process (AHP) to rank models according to their understandability. The results indicate that decision tree models are perceived as more understandable than rule-based models. Using the survey results regarding understandability of a number of models in conjunction with quantitative measurements of the complexity of the models, we are able to establish a negative correlation between the complexity and understandability of the classification models, at least for one of the two studied data sets.

The random forest algorithm belongs to the class of ensemble learning methods that are embarassingly parallel, i.e., the learning task can be straightforwardly divided into subtasks that can be solved independently by concurrent processes. A parallel version of the random forest algorithm has been implemented in Erlang, a concurrent programming language originally developed for telecommunication applications. The implementation can be used for generating very large forests, or handling very large datasets, in a reasonable time frame. This allows for investigating potential gains in predictive performance from generating large-scale forests. An empirical investigation on 34 datasets from the UCI repository shows that forests of 1000 trees significantly outperform forests of 100 trees with respect to accuracy, area under ROC curve (AUC) and Brier score. However, increasing the forest sizes to 10 000 or 100 000 trees does not give any further significant performance gains.

In real-life machine learning applications, there are often costs associated with the features needed in prediction. This is the case for example when deploying learned models in mass produced products, where the manufacturing costs or space limitations may restrict the number of feature extracting sensors that can be included in each device. In such situations, the training process involves a sparsity budget restricting the number of features the learned predictor can use. In this paper, we consider the problem of learning multi-label predictors under a sparsity budget. For this purpose, we consider three different wrapper-based greedy forward selection approaches for constructing sparse multi-label learning models. In our experiments, we show that the method selecting a common set of features shared by multiple tasks by greedily maximizing the prediction performance averaged over all the tasks provides a better prediction performance than the approaches selecting the features separately for each task.

Machine learning techniques typically result from the need for intelligent solutions to practical tasks. Nowadays, large data volumes are usually involved and machine learning techniques are focused on particular tasks like classification, regression or clustering. For the latter task, clustering, quite a few algorithms have been proposed, typically tailored to particular application domains and their data sets. Recently, georeferenced (or spatial) data sets keep emerging in lots of disciplines. Therefore, algorithms which are able to handle these spatial data sets should be developed. This article shortly describes a particular application area, precision agriculture, and the spatial data sets which exist there. A particular task from this area, management zone delineation, is outlined and existing spatial clustering algorithms are evaluated for this task. Based on the experiences with those algorithms and a few requirements, HACC-SPATIAL is developed. The algorithm is based on hierarchical agglomerative clustering with a spatial constraint and it is demonstrated to produce practically advantageous results on precision agriculture data sets.

Parallel planning deals with the problem of finding a sequence of sets of independent actions such that the traditional plan is obtained by ordering actions in these sets. Parallel plans are frequently used by planners based on transformation of the planning problem to a different solving formalism such as SAT (Boolean satisfiability) or CP (Constraint Programming). In this paper we propose a modification of the constraint model for parallel planning based on different encoding of action transitions. Rather than encoding states and their changes via actions, we suggest to encode directly transitions between the actions and omit completely the state variables. This novel encoding improved significantly the runtime of the planner due to faster inference which is demonstrated experimentally using planning domains from International Planning Competition.

Trajectory (path) planning is a well known and thoroughly studied field of automated planning. It is usually used in computer games, robotics or autonomous agent simulations. Grids are often used for regular discretization of continuous space. Many methods exist for trajectory (path) planning on grids, we address the well known A* algorithm and the state-of-the-art Theta* algorithm. Theta* algorithm, as opposed to A*, provides ‘any-angle’ paths that look more realistic. In this paper, we provide an extension of both these algorithms to enable support for speed limit constraints. We experimentally evaluate and thoroughly discuss how the extensions affect the planning process showing reasonability and justification of our approach.

This paper presents a safe learning strategy for continuous state and action spaces by utilizing Lyapunov stability properties of the studied systems. The reinforcement learning algorithm Continous Actor-Critic Learning Automation (CACLA) is combined with the notion of control Lyapunov functions (CLF) to limit the learning and exploration behavior to operate inside the stability region of the system to ensure safe operation at all times. The paper extends previous results for discrete action sets to take advantage of the more general continuous actions sets, and show that the continuous method is able to find a comparable solution to the best discrete action choices while avoiding the need for good heuristic choices in the design process.

Monte Carlo Tree Search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems, typically move planning in combinatorial games. It combines the generality of random simulation with the precision of tree search. It can theoretically be applied to any domain that can be described in terms of state, action pairs and simulation used to forecast outcomes such as decision support, control, delayed reward problems or complex optimization. The motivation behind this work is caused by the emerging GPU-based systems and their high computational potential combined with relatively low power usage compared to CPUs. As a problem to be solved we chose to develop an AI GPU(Graphics Processing Unit)-based agent in the game of Reversi (Othello) which provides a sufficiently complex problem for tree searching with non-uniform structure and an average branching factor of over 8. We present an efficient parallel GPU MCTS implementation based on the introduced ‘block-parallelism’ scheme which combines GPU SIMD thread groups and performs independent searches without any need of intra-GPU or inter-GPU communication. We compare it with a simple leaf parallel scheme which implies certain performance limitations. The obtained results show that using my GPU MCTS implementation on the TSUBAME 2.0 system one GPU can be compared to 100-200 CPU threads depending on factors such as the search time and other MCTS parameters in terms of obtained results. We propose and analyze simultaneous CPU/GPU execution which improves the overall result.

The task of enforcing certain level of consistency in Boolean satisfiability problem (SAT problem) is addressed in this paper. The concept of path-consistency known from the constraint programming paradigm is revisited in this context. Augmentations how to make path-consistency more suitable for SAT are specifically studied. A stronger variant of path-consistency is described and its theoretical properties are investigated. It combines the standard path consistency on the literal encoding of the given SAT instance with global properties calculated from constraints imposed by the instance – namely with the maximum number of visits of a certain set by the path. Unfortunately, the problem of enforcing this variant of path-consistency turned out to be NP hard. Hence, various types of relaxations of this stronger version of path-consistency were proposed. The relaxed version of the proposed consistency represents a trade-off between the inference strength and the complexity of its propagation algorithm. A presented theoretical analysis shows that computational costs of the proposed consistency are kept reasonably low. Performed experiments show that the new consistency outperforms the standard path-consistency in terms of the inference strength as well.

We have designed a framework for Bayesian Statistical Anomaly Detection, called ISC, or Incremental Stream Clustering. It learns the normal situation incrementally, and can on the fly detect anomalous cases. When this happens, a new cluster can be created, so similar cases can be detected in the future. In this way, the framework performs incremental clustering, while at the same time either classifying a new case as belonging to one of the known clusters or indicating that it is from a previously unseen situation.

In this study, lung tumour motion modelling and prediction was done using a fuzzy logic approach. The surrogate signal for breathing motion was obtained from 10 different instances of a lung patient by using signals from Realtime Respiratory Motion Management (RPM) system. A regularity criterion (RC criterion) was used to select appropriate inputs for the model for each trace. A first order Sugeno type model was devised by using a subtractive clustering approach. On an average, the prediction error was seen to be 0.21 mm for training and 0.23 mm for testing. The two main advantages of using a fuzzy logic approach are reduction in the input data to enable faster model building and linguistic interpretability for easier clinical use.

Fish farmers manage assets of considerable value on a daily basis. Many aspects of the daily operation are automated in some way, such as the feeding system. Sensory equipment steadily becomes cheaper and more ubiquitous, yielding data that can be used by automated systems and for post-processing (i.e. data mining) to discover hidden trends in the data. However, a lot of information is only known informally by the fish farmers themselves, through years of experience. Companies that can store this information and reuse it will have an advantage; even more so if high-level human expertise can be linked to low-level sensor data. This paper presents early developments of a system that stores this informal knowledge using case based-reasoning, combined with corresponding sensor data.

This paper gives an overview of different methods for automated fault detection. Emphasis will be put on the properties of model based techniques (which we will further divide into analytical model based and knowledge based), multivariate statistical process control and machine learning techniques. The machine learning techniques are not traditionally viewed as a standard method for fault detection, so they are especially highlighted in this paper. Each method is presented in detail, and we will also discuss alternative extensions for various applications. The paper is ended by proposing to use machine learning techniques as a robust and well-functioning method in general.

This concept paper describes a novel approach to view-independent human gait analysis. Previous work in computer vision-based gait analysis typically use silhouette images from one side-view camera as input to the recognition system. Our approach utilises multiple synchronised cameras placed around the subject. From extracted silhouette images a 3D reconstruction is done that produces a segmented, labelled pose tree. Features are extracted from the pose tree and combined into an input case to the Case-Based Reasoning system. The input case is matched against stored past cases in a case base, and the most similar cases are classified by a Hidden Markov Model. The advantages of this approach are that subjects can be captured in a completely view-invariant way and recognition is efficient because unlikely candidates can be quickly discarded.

An autonomous robot which is equipped with sensorimotor loops and situated within a specific environment can be regarded as a dynamical system. By using Attractor-Based Behavior Control (ABC), the attractors of this dynamical system correspond to energy-efficient behavioral body postures, and the attractor-connecting heteroclinic orbits can be utilized to generate stable motion trajectories. We introduce ABC-Learning and demonstrate how it enables an autonomous robot to self-explore its behavioral capabilities from scratch and without any given body model.

This article describes results of the work on knowledge representation techniques chosen for use in the European project SIARAS (Skill-Based Inspection and Assembly for Reconfigurable Automation Systems). Its goal was to create intelligent support system for reconfiguration and adaptation of robot-based manufacturing cells. Declarative knowledge is represented first of all in an ontology expressed in OWL, for a generic taxonomical reasoning, and in a number of special-purpose reasoning modules, specific for the application domain. The domaindependent modules are organized in a blackboard-like architecture.

We present a bimodal model able to internally simulate expected sequences of perceptions within a modality likely to follow the last sensory experience. Simultaneously reasonable perceptual expectations are elicited in the other modality. Our model is based on the novel Associative Self-Organizing Map (A-SOM), which develops a representation of the input space as well as learns to associate its activity with the (possibly time delayed) activities of an arbitrary number of other neural networks. The model was trained on sequences of inputs and the trained model was able to simulate appropriate sequences of activity patterns in the absence of sensory input for several epochs in both modalities. The simulation results are very encouraging and confirms the abilities of the A-SOM to serve in a multimodal system capable of internal simulation of perceptions and of cross-modal expectations.