Science and Innovation mission to Japan

Sue Kinoshita, Minister Counsellor economic affairs and Professor Quigley

This week Professor Quigley joined a mission to Japan with other academics from the University of Oxford, Edinburgh, UCL and Manchester. The week long event was organised by the UK’s Science and Innovation team in Japan, part of the Foreign and Commonwealth Office. Over five days the delegation visited and presented at seven companies along with three seminars and workshops. Across nine presentations Professor Quigley presented to hundreds of people and introduced some of the Human Computer Interaction research in SACHI, along with research from the AI research group. This mission has the goal to strengthen research collaboration and innovation partnership between the UK and Japan.

During his talks, Aaron provided examples from our engineering doctorate program, our MSc program, work on research interns, PhD students and academics from across Computer Science.

 

Sethu Vijayakumar, Edinburgh University, Sue Kinoshita, Minister Counsellor economic affairs, Professor Aaron Quigley, Seiichi Asano, Senior science Officer and Joesph Robertson, Science & Innovation Officer.

Griff Jones, First Secretary, science innovation & global challenges, Sethu Vijayakumar, Edinburgh University, Sue Kinoshita, Minister Counsellor economic affairs, Professor Aaron Quigley, Seiichi Asano, Senior science Officer and Joesph Robertson, Science & Innovation Officer.

The next big thing or the next big gimmick?

Dr Tom Kelsey will be holding a panel discussion at Computing’s first ever Artificial Intelligence and Machine Learning Live conference on Monday 19th November in London. Through a variety of expert key-notes, end-user case studies, and panel discussions the conference will highlight key developments within AI.

Tom’s panel discussion: The next big thing or the next big gimmick?
Read more about the conference and programme of events at
http://events.computing.co.uk/computingai/programme

Fable-based Learning: Seminar by Prof Jimmy Lee

Event details

  • When: 21st August 2018 13:30 - 14:30
  • Where: Cole 1.33b
  • Format: Seminar

CUHK + UniMelb = Fable-based Learning + A Tale of Two Cities

Prof Jimmy Lee, Chinese University of Hong Kong

This talk reports on the pedagogical innovation and experience of a joint venture by The Chinese University of Hong Kong (CUHK) and the University of Melbourne (UniMelb) in the development of MOOCs on the computer science subject of “Modeling and Solving Discrete Optimization Problems”.  In a nutshell, the MOOCs feature the Fable-based Learning approach, which is a form of problem-based learning encapsulated in a coherent story plot.  Each video lecture begins with an animation that tells a story based on the Chinese classic “Romance of the Three Kingdoms”, in which the protagonists in the novel encounter a problem requiring technical assistance from the two professors from modern time via a magical tablet bestowed upon them by a fairy god.  The new pedagogy aims at increasing learners’ motivation as well as situating the learners in a coherent learning context.  In addition to scriptwriting, animation production and situating the teaching materials in the story plot, another challenge of the project is the remote distance and potential cultural gap between the two institutions as well as the need to produce all teaching materials in both (Mandarin) Chinese and English to cater for different geographical learning needs.  The MOOCs have been running recurrently on Coursera since 2017.  Some learner statistics and feedbacks will be presented.  The experience and preliminary observations of adopting the online materials in a Flipped Classroom setting at CUHK will also be detailed.

This video at Youtube shows the trailer for the Coursera Course:

Biography:

Jimmy Lee has been on the faculty of The Chinese University of Hong Kong since 1992, where he is currently the Assistant Dean (Education) in the Faculty of Engineering and a Professor in the Department of Computer Science and Engineering.  His major research focuses on constraint satisfaction and optimization with applications in discrete optimization, but he is also involved in investigating ways of improving students’ learning experience via proper use of technologies.  Jimmy is a two-time recipient (2004 and 2015) of the Vice-Chancellor’s Exemplary Teaching Award and most recently the recipient of the University Education Award (2017) at CUHK.

Seminar: SMT, Planning and Snowmen

Event details

  • When: 6th August 2018 11:00 - 12:00
  • Where: Cole 1.33a
  • Series: AI Seminar Series
  • Format: Seminar

Professor Mateu Villaret, from Universitat de Girona is a visiting scholar with the AI group from July 1st until September 30th. Professor Villaret works on algorithms for routing and scheduling with the AI group at St Andrews.

As well as solving practical problems, he also enjoys puzzle games. That is the basis of this talk, about using Planning and SMT to solve the “Snowman” puzzle.

Seminar: AI-augmented algorithms — how I learned to stop worrying and love choice

The speaker is Lars Kotthoff, previously a PhD student here, now and Assistant Professor at the University of Wyoming. All welcome.

 

Often, there is more than one way to solve a problem. It could be a different
parameter setting, a different piece of software, or an entirely different
approach. Choosing the best way is usually a difficult task, even for experts.
AI and machine learning allow to leverage performance differences of
algorithms (for a wide definition of “algorithm”) on different problems and
choose the best algorithm for a given problem automatically. In AI itself,
these techniques have redefined the state of the art in several areas and led
to innovative approaches to solving challenging problems.

In this talk, I will give examples of how AI can help to solve challenging
computational problems, what techniques have been applied, and how you can do
the same. I will argue that AI has fundamental implications for software
development, engineering, and computer science in general — stop making
decisions when coding, having more algorithmic choices is better!

 

SRG Seminar: “Interactional Justice vs. The Paradox of Self-Amendment and the Iron Law of Oligarchy” by Jeremy Pitt

Event details

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

Self-organisation and self-governance offer an effective approach to resolving collective action problems in multi-agent systems, such as fair and sustainable resource allocation. Nevertheless, self-governing systems which allow unrestricted and unsupervised self-modification expose themselves to several risks, including the Suber’s paradox of self-amendment (rules specify their own amendment) and Michel’s iron law of oligarchy (that the system will inevitably be taken over by a small clique and be run for its own benefit, rather than in the collective interest). This talk will present an algorithmic approach to resisting both the paradox and the iron law, based on the idea of interactional justice derived from sociology, and legal and organizational theory. The process of interactional justice operationalised in this talk uses opinion formation over a social network with respect to a shared set of congruent values, to transform a set of individual, subjective self-assessments into a collective, relative, aggregated assessment.

Using multi-agent simulation, we present some experimental results about detecting and resisting cliques. We conclude with a discussion of some implications concerning institutional reformation and stability, ownership of the means of coordination, and knowledge management processes in ‘democratic’ systems.

Biography
Photograph of Professor Jeremy Pitt
Jeremy Pitt is Professor of Intelligent and Self-Organising Systems in the Department of Electrical & Electronic Engineering at Imperial College London, where he is also Deputy Head of the Intelligent Systems & Networks Group. His research interests focus on developing formal models of social processes using computational logic, and their application in self-organising multi-agent systems, for example fair and sustainable common-pool resource management in ad hoc and sensor network. He also has strong interests in human-computer interaction, socio-technical systems, and the social impact of technology; with regard to the latter he has edited two books, This Pervasive Day (IC Press, 2012) and The Computer After Me (IC Press, 2014). He has been an investigator on more than 30 national and European research projects and has published more than 150 articles in journals and conferences. He is a Senior Member of the ACM, a Fellow of the BCS, and a Fellow of the IET; he is also an Associate Editor of ACM Transactions on Autonomous and Adaptive Systems and an Associate Editor of IEEE Technology and Society Magazine.

n-Queens Completion is NP-Complete

Peter Nightingale and Ian Gent at Falkland Palace, Wednesday, 17 August 2017.
©Stuart Nicol Photography, 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.

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 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

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

Event details

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

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]

Success in the Laidlaw Undergraduate Internship Programme in Research and Leadership

Congratulations to Patrick Schrempf and Billy Brown who have been successful in their applications for a Laidlaw Undergraduate Internship in Research and Leadership for 2017. You can read further details about Billy and Patrick below.

Billy Brown:

I’m a fourth year Computer Science student from Belgium with too much interest for the subject. I play and referee korfball for the university, and I am fascinated by Old English and Norse history and mythology. I plan on using the Laidlaw Internship programme to get into the field of Computer Science research.

Project summary:

The Essence Domain Inference project aims to improve automated decision making by optimising the understanding of the statements used to define a problem specification. As part of the compilation of the high level Essence specification language, this project would tighten the domains to which a specified problem applies, with a domain inference algorithm.

The work is very much in the context of the recently-announced EPSRC grant working on automated constraint modelling in an attempt to advance the state of the art in solving complex combinatorial search problems. The modelling pipeline is akin to a compiler in that we refine a specification in the Essence language Billy mentions down to a number of powerful solving formalisms. The work Billy plan is to improve the refinement process and therefore the performance of the solvers, leading to higher quality solutions more quickly.

Patrick Schrempf:
I am currently a third year Computer Science student from Vienna. After enjoying doing research with the St Andrews Computer Human Interaction (SACHI) group last year, I am looking forward to the Laidlaw Internship Programme. Apart from research and studying, I enjoy training and competing with the Triathlon Club and the Pool Society.
Continue reading