iVoLVER receives Best Demo Jury Award at ACM ISS

The iVoLVER system, created by Gonzalo Méndez and Miguel Nacenta from the SACHI group at the School of Computer Science, University of St Andrews, received Best Demo Jury Award at the ACM Interactive Surfaces and Spaces (ACM ISS) conference last week.

ACM ISS 2017, took place in Brighton, UK and selects a different location each year, with Tokyo, Japan selected as next year’s destination. The conference is a premier venue for research that studies how people interact in smart spaces and surfaces and how to design and engineer solutions for novel interfaces.

iVoLVER is a web-based visual programming environment that enables anyone to transform visualizations that they find in-the-wild (e.g., in a poster or a newspaper) into new visualizations that are more useful for them. Congratulations to the iVoLVER team. You can try out the open source iVoLVER prototype using a browser.

An example iVoLVER interface

Best Demo Jury Award

“A Decentralised Multimodal Integration of Social Signals: A Bio-Inspired Approach” by Esma Benssassi and “Plug and Play Bench: Simplifying Big Data Benchmarking Using Containers” by Sheriffo Ceesay

Esma’s abstract

The ability to integrate information from different sensory modalities in a social context is crucial for achieving an understanding of social cues and gaining useful social interaction and experience. Recent research has focused on multi-modal integration of social signals from visual, auditory, haptic or physiological data. Different data fusion techniques have been designed and developed; however, the majority have not achieved significant accuracy improvement in recognising social cues compared to uni-modal social signal recognition. One of the possible limitations is that these existing approaches have no sufficient capacity to model various types of interactions between different modalities and have not been able to leverage the advantages of multi-modal signals by considering each of them as complementary to the others. We introduce ideas for creating a decentralised model for social signals integration inspired by computational models of multi-sensory integration in neuroscience and the perception of social signals in the human brain.

Sheriffo’s abstract

The recent boom of big data, coupled with the challenges of its processing and storage gave rise to the development of distributed data processing and storage paradigms like MapReduce, Spark, and NoSQL databases. With the advent of cloud computing, processing and storing such massive datasets on clusters of machines is now feasible with ease. However, there are limited tools and approaches, which users can rely on to gauge and comprehend the performance of their big data applications deployed locally on clusters, or in the cloud. Researchers have started exploring this area by providing benchmarking suites suitable for big data applications. However, many of these tools are fragmented, complex to deploy and manage, and do not provide transparency with respect to the monetary cost of benchmarking an application.

In this talk, I will present Plug And Play Bench PAPB (https://github.com/sneceesay77/papb): an infrastructure aware abstraction built to integrate and simplify the process of big data benchmarking. PAPB automates the tedious process of installing, configuring and executing common big data benchmark workloads by containerising the tools and settings based on the underlying cluster deployment framework. Our proof of concept implementation utilises HiBench as the benchmark suite, HDP as the cluster deployment framework and Azure as the cloud platform. The talk will further illustrate the inclusion of cost metrics based on the underlying Microsoft Azure cloud platform.

Event details

  • When: 26th October 2017 13:00 - 14:00
  • Where: Cole 1.33a
  • Series: Systems Seminars Series
  • Format: Seminar

SRG Seminar: “Adaptive Multisite Computation Offloading in Mobile Clouds” by Dawand Sulaiman and “Topological Ranking-Based Resource Scheduling for Multi-Accelerator Systems” by Teng Yu

Dawand’s abstract

The concept of using cloud hosted infrastructure as a means to overcome the resource-constraints of mobile devices is known as Mobile Cloud Computing (MCC), and allows applications to run partially on the device, and partially on a remote cloud instance, thereby overcoming any device-specific resource constraints. However, as smart phones and tablets gain more CPU power and longer battery life, the meaning of MCC gradually changes. Instead of being fully dependent on the cloud, a number of nearby devices can be used to coordinate and distribute content and resources in a decentralised manner; this is known as Mobile Ad hoc Cloud Computing. Mobile devices with less computational power and lower battery life can be leveraged by the nearby mobile devices to run resource-intensive applications. Therefore, more efficient and reliable methodologies need to be explored for resource hungry and real time applications such as face recognition, data-intensive, and augmented reality mobile applications.
We present a unified framework which allows each mobile device within the shared environment to intelligently offload its computation to other external platforms. For the individual mobile devices, it is important to make the offloading decision based on network conditions, load of other machines, and mobile device’s own constraints (e.g., mobility and battery). Moreover, to achieve a global optimal task completion time for tasks from all the mobile devices, it is necessary to devise a task scheduling solution that schedules offloaded tasks in real time. The offloading decision engine needs to adapt to the dynamic changes in both the host device and connected nearby and remote devices.

Teng’s abstract

Accelerators are becoming increasingly prevalent in distributed computation. FPGAs have been shown to be fast and power efficient for particular tasks, yet scheduling on multi-accelerator systems is challenging when workloads vary significantly in granularity in terms of task size and/or number of computational unit required.
We present a novel approach for dynamically scheduling tasks on networked multi-accelerator systems which maintains high performance, even in the presence of irregular jobs. Our topological ranking-based scheduling allows realistic irregular workloads to be processed while maintaining a significantly higher level of performance than existing schedulers.

Event details

  • When: 12th October 2017 13:00 - 14:00
  • Where: Cole 1.33b
  • Series: Systems Seminars Series
  • Format: Seminar

SRG Seminar: “Simulating a pulmonary tuberculosis infection using a network-based metapopulation model” by Michael Pitcher and “A Fake City of People: Modeling the Co-evolution of City and Citizens” by Xue Guo

Event details
When: 28th September 2017 13:00 – 14:00
Where: Cole 1.33b
Series: Systems Seminars Series
Format: Seminar

Michael Pitcher’s abstract

Tuberculosis (TB) is one of the world’s most deadly infectious diseases, claiming over 1.4 million lives every year. TB infections typically affect the lungs and treatment regimens are long and arduous, requiring at least 6 months of daily chemotherapy. Previous investigations have shown TB to have unique localisations within the lung at varying stages of infection. The initial implant and the primary lesion which arises from it can occur anywhere in the lungs, with a greater probability of occurrence in the lower to middle regions of the lung. However, reactivation of a previously latent form of disease always involves cavitation of the tissue at the apical regions. This difference in spatial location of TB infections suggests two important factors: i) bacteria are able to disseminate across the lung in some manner, and ii) the environment at the top of the lung has some properties that make it preferential for TB replication.

In this project, we aim to build a whole-organ model of the lung and surrounding lymphatics which incorporates both bacterial dissemination possibilities and lung tissue spatial heterogeneity in order to understand their impact on TB. We develop ComMeN (Compartmentalised Metapopulation Network), a Python framework designed to allow the easy creation of complex network-based metapopulations with spatial heterogeneity upon which interaction dynamics can be applied, with discrete event modelling using the Gillespie Algorithm. We then extend this framework to create a TB-specific model, PTBComMeN, which models a TB infection occurring over lung tissue which is divided into patches, each of which contains spatial attributes appropriate to its position in the lung, such as ventilation, perfusion and oxygen tension. Events dictate the interactions between cells and bacteria and their interaction with the environment, with dissemination occurring between edges joining patches on the lung network. This model allows experimentation into studying the effects spatial heterogeneities and bacterial dissemination may have on the progression of disease and the model is designed to provide insight into the factors that result in long treatment times for TB.

Xue Guo’s abstract

By the year 2050, the global urban population will reach 2.5 billion. While the fast pace of urbanisation brings improved quality of life initially, the surging population will inevitably lead to unique urban issues. Emerging research fields, with the aim of creating smarter cities, plan to counteract these problems. To facilitate this research, we need solid models to generate ’fake cities’, which cannot be easily produced by existing random graph algorithms due to spatial constraints. Therefore, we propose a new model for the co-evolution of city and population, which can show how street network forms, how population spreads and how settlements emerge and diminish. The new model will be a random city generator, which could be used to backtrack the history and predict the future of a city, or act as test cases for the validation and evaluation of urban optimisation algorithms.

Event details

  • When: 28th September 2017 13:00 - 14:00
  • Where: Cole 1.33b
  • Series: School Seminar Series, Systems Seminars Series
  • Format: Seminar

n-Queens Completion is NP-Complete

Update, 2021

Over the years since we published this research, many people have approached us having solved the n queens puzzle, either for one n like 8 or 1000, or having written an algorithm to solve it for different sizes.  Unfortunately this is not a major result in Computer Science and does not make one eligible to claim the $1M Clay prize. Many have been disappointed by this so we want to clarify why  this is the case. 

It is true that work on this problem could potentially result in the award but only if some exceptionally difficult conditions are met.

  • EITHER prove mathematically that NO possible algorithm could solve the n queens completion problem in polynomial time;
  • OR prove that there is an algorithm which is guaranteed to solve every instance of the n queens completion problem in polynomial time. Note that in this case the algorithm has to work on the completion version of the problem studied in our paper, not placing queens on an empty board; the algorithm has to give the correct answer on every possible instance given to it; and there has to be a mathematical proof that the algorithm’s runtime is bounded above by some polynomial in the size of the board.  However fast a given algorithm runs when tested, this is not sufficient because there are an infinite number of possible tests available, so a mathematical proof is required.
  • AND in either case, prove this at a level that is published in a respected academic source and is widely accepted by research experts as correct.

We are delighted that our work has led so many people to be interested in the problem of solving problems like the n queens puzzle that fascinates us.  But we also apologise for any impression we gave, unintentionally, that a solution to the n queens puzzle could lead to the award of the prize except under the extremely strenuous conditions listed above.

Ian Gent, 10 May 2021

Original Post from 2017:

Ian Gent, Christopher Jefferson and Peter Nightingale have shown that a classic chess puzzle is NP-Complete. Their paper “Complexity of n-Queens Completion” was published in the Journal of Artificial Intelligence Research on August 30, 2017.

The n-Queens puzzle is a classic chess problem: given a chessboard of size n by n, can you place n queens so that no two queens attack each other?  That is, can you place the queens with no two queens are on the same row, column, or diagonal? The n-Queens puzzle has long been known to be simple to solve:  you can solve the problem for all n except 2 and 3, and solutions for all other n can be described in a few lines.  This very simplicity has led to repeated

Peter Nightingale and Ian Gent at Falkland Palace, Wednesday, 17 August 2017.
©Stuart Nicol Photography, 2017

controversy in Artificial Intelligence (AI). The n-Queens puzzle is often used as a benchmark problem, but good results on the problem can always be challenged because the problem is so simple to solve without using AI methods.

The new work follows a challenge on Facebook on New Year’s Day, 2015, when a friend of Ian’s asked him how hard n-Queens is if some queens were already placed on the board.  It turns out, this version (dating from 1850) of the puzzle is only two years younger than the more famous n-Queens problem. The picture shows Peter (left) and Ian (right) with queens on the board at positions suggested by Nauck in 1850, the squares b4 and d5.  Can you put another 6 queens on the board so that the entire board is a solution of 8-Queens?  The general version with some number of queens preplaced on an n by n board is the n-Queens Completion puzzle.

 

With queens at b4 and d5, can you place 6 more queens to get a solution to the 8-queens puzzle? ©Stuart Nicol Photography, 2017

Ian, Christopher and Peter have shown that the n-Queens puzzle is in fact hard, not simple.  It belongs to the complexity classes NP-Complete and #P-Complete. Other NP-Complete problems include the “travelling salesperson problem”, finding cliques in graphs, and many other important problems, from scheduling to circuit layout. This puts n-Queens Completion at the centre of the most important theoretical problem in computer science — it has long been known that either all NP-complete problems are easy, or none of them are. Most computer scientists believe that this means there is no efficient algorithm possible for solving this problem, compared to the very simple techniques long known for n-Queens.
The importance of this work is that it provides researchers with a benchmark that can be used for evaluating AI techniques. Moreover, it helps to explain why so many AI techniques have been used on the n-Queens puzzle. Most techniques do most of their work with some queens partially placed, using some form of (hopefully intelligent) trial and error. In fact it turns out that many researchers – in order to solve a simple problem – have solved it by turning the simple problem of n-Queens into the hard problem of n-Queens Completion.
It does seem that AI researchers should not use n-Queens as a benchmark, but the very closely related n-Queens Completion puzzle is a valid benchmark. As well as the theoretical results, the paper shows how example instances can be generated which appear to be hard in practice. Some caution is still needed, though. It does seem to be quite hard to generate hard instances of n-Queens Completion.
The University has also issued an article on the same paper, under the title “Simple” chess puzzle holds key to $1m prize

Containers for HPC environments

Rethinking High performance computing Platforms: Challenges, Opportunities and Recommendations, co-authored by Adam Barker and a team (Ole Weidner, Malcolm Atkinson, Rosa Filgueira Vicente) in the School of Informatics, University of Edinburgh was recently featured in the Communications of the ACM and HPC Wire.

The paper focuses on container technology and argues that a number of “second generation” high-performance computing applications with heterogeneous, dynamic and data-intensive properties have an extended set of requirements, which are not met by the current production HPC platform models and policies. These applications (and users) require a new approach to supporting infrastructure, which draws on container-like technology and services. The paper then goes on to describe cHPC: an early prototype of an implementation based on Linux Containers (LXC).

Ali Khajeh-Hosseini, Co-founder of AbarCloud and former co-founder of ShopForCloud (acquired by RightScale as PlanForCloud) said of this research, “Containers have helped speed-up the development and deployment of applications in heterogeneous environments found in larger enterprises. It’s interesting to investigate their applications in similar types of environments in newer HPC applications.

DHSI Seminar Series (Digital Health Science Initiative)

“Addiction”

Seminar Room 1 School of Medicine

12:00: Alex Baldacchino- Introduction

12:15: Ognjen Arandjelović & Aniqa Aslam- Understanding Fatal and Non-Fatal Drug Overdose Risk Factors in Fife: Overdose Risk (OdRi) tool

12:45: Damien Williams & Fergus Neville- Transdermal alcohol monitoring

13:15: David Harris-Birtill & David Morrison- Narco Cat – waste water analysis in substance misuse – a novel epidemiological tool

13:15 – 14.00: All Questions & Opportunities

Event details

  • When: 14th June 2017 12:00 - 14:00
  • Where: N Haugh, St Andrews
  • Format: Seminar

Seminar: Propagation and Reification: SAT and SMT in Prolog (continued)

Jacob Howe, City University, London

Abstract: This talk will recap how a watched literal DPLL based SAT solver can be succinctly coded in 20 lines of Prolog. The focus of the talk will be the extension of this solver to an SMT solver which will be discussed with a particular focus on the case where the theory is that of rational-tree constraints, and its application in a reverse engineering problem.
[Note change of time from that previously advertised]

Event details

  • When: 23rd June 2017 13:00 - 14:00
  • Where: Cole 1.33a
  • Series: AI Seminar Series
  • Format: Seminar