PATAT 2010: Multi-objective Sports (Football) Scheduling

At the recent PATAT (8th International Conference on the Practice and Theory of Automated Timetabling) conference I was fortunate enough to be invited to give a plenary presentation.

My talk focussed on sports scheduling. Indeed, the title was "Scheduling Football (Soccer) Fixtures: Progress Made to Date and Future Challenges". I focussed on the conflicting objectives when trying to minimise travel distances, whilst also trying to reduce pair clashes (which can be considered as local derbies for the sake of this discussion).

This is a classic case of a multi-objective problem where minimising one objective causes the other to increase and vice versa. It is not (usually) possible to minimise both objectives, instead you are looking for a trade off. These are plotted on a pareto front where a user would then decide which trade off solution is the best.

In the plenary talk, I showed that it was possible to reduce both the distance and the pair clashes such that (sometimes) the distance did not significantly increase. This is a potentially useful result as it means that supporters do not have to travel any further (statistically) and the policing costs are reduced as they do not have to police so many local derbies.

I should say that this result is only work in progress at the moment in that it has not been verified by the football authorites or the police, but I would hope that it would be of interest to them.

In the same talk, I also discussed how I collected the data for this work (which essentially is the various distances between football clubs). This involved using Google maps and Multimap APIs. I'll talk about this in the next blog. I'll also provide a link to the paper (as I don't have it to hand at the moment). But, if you are interested the reference is:

Kendall G., McCollum B., Cruz F. and McMullan P. (2010) Scheduling English Football Fixtures: Consideration of Two Conflicting Objectives. In proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2010), 11-13 August 2010, Queen’s University, Belfast, UK, pp 1-15

2010 Pac-Man Competition at CIG 2010

Last week I attended the IEEE Conference on Computational Intelligence and Games (CIG 2010). This conference (it was actually a symposium in the early days) was started by Simon Lucas and myself in 2005. I also co-chaired the conference with Susil Louis in 2006. The conference has been run every year since 2005, with the lastest one being held in Copenhagen, chaired by Georgios N. Yannakakis and Julian Togelius.


This year I had a paper that was developed as part of a 2nd Year Group Project (the teams members are shown in the picture).

As part of the Computer Science undergraduate degree at the University of Nottingham, second year students are assigned to groups and given a software engineering task to work on. Last year, I set the following:


Your task is to write a computer program that can play the game of Pacman, without human intervention. This is a challenging task and, without some support would, perhaps, be impossible for a second year group project. However, this task has been an ongoing competition for a number of years and there is lots of information/support available, as well as examples as to what can be achieved.

Your starting point should be the web pages of Professor Simon Lucas at the University of Essex, who organises the competition. Therefore, take a look at this web page. This is ESSENTIAL reading and you should study this page (and associated links) before our first meeting. You should also make regular visits to the page as I know that Professor Lucas is planning to update it on a regular basis. Using the information on this web site you should be able to get a system up and running quite quickly and then you have to develop your own algorithms to produce the best automated player that you can.

I would expect you to carry out (at least) the following tasks, with the first two feeding directly into your literature review:

By referencing the competition entries, find out what algorithms appear to have worked well in the past.

Investigate and draw up a set of algorithms that you think could be used as a Pacman Controller. These algorithms might be based on various criteria such as those identified in 1 (above), "Manhattan Distance", "Straight Line Distance", "Trying to eat the ghosts", "Trying to avoid the ghosts", "Trying to eat the fruit", "Maximising the score, whilst minimising your chances of being eaten", etc. There is probably not one good overall strategy and you might consider changing strategies as the game state changes. You might also want to consider how much you plan ahead and how much you just make quick decisions, given that this is a real time game.

As part of the supplied toolkit you are provided with screen capture software (and a window showing you a representation of the captured game state), the game screen itself and a small screen showing the current direction of the Pacman character. As part of this project, I would also like you to develop another GUI element which enables you to select from amongst the algorithms that you have implemented, keeps track of their high score, enables you to choose how "adventurous" the player will be, enables you to mix/match the algorithms etc. Part of the project will be to design this GUI element, deciding what role it should play in the overall software architecture. You can then use this captured information as a basis for the analysis in your final dissertation.

Implement the int move(GameState gs) that is provided in the sample toolkit in order to test out the various game playing algorithms that you have investigated in points 1 and 2 above.


You might want to look at look at the YouTube Video for the competition entry from WCCI 2008 (google "YouTube WCCI pacman"). To give you some indication of the current state of the art, the most recent competition (run in Milan in August 2009), the winning entry achieved a score over 30,000 and reached (from memory) level 5 (it might have been level 4). If you can get anywhere near that you will be doing very well.


The project group did so well that the team not only won the prize for the best project but the School also agreed to fund one of the team members to attend the conference to enter the competition. As a result we also wrote a paper which was a accepted at the conference and the student presented it (a big undertaking for an undergraduate student, but he did very well).

In the competition, we came a VERY respectable third. In second place were last years winners. In first place was a new team who used an Ant Colony based method.

The difference between the top three entries was not that large, with the winning entry getting about 21,000 points.

In fact, during pre-competition testing our team achieved scores of over 22,000 on many occasions, with our best ever score being just over 30,000 (I am sure that the other entrants also have similar sob stories to tell :-)).

If you are interested the reference for our paper is.

Bell N., Fang X., Hughes R., Kendall G., OReilly E. and Qiu S. (2010) Ghost Direction Detection and other Innovations for Ms. Pac-Man. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG'10), 18-21 Aug 2010, Copenhagen, Denmark, pp 465-472

It can be downloaded from here.

The references for the first and second placed entries are.

1. Emilio M., Moises M., Gustavo R. and Yago S. (2010) Pac-mAnt: Optimization Based on Ant Colonies Applied to Developing an Agent for Ms. Pac-Man. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG'10), 18-21 Aug 2010, Copenhagen, Denmark, pp 458-464
2. Thawonmas R. and Ashida T. (2010 Evolution Strategy for Optimizing Parameters in Ms Pac-Man Controller ICE Pambush 3. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG'10), 18-21 Aug 2010, Copenhagen, Denmark, pp 235-240

More details about the Pac-Man competition can be found at Simon Lucas' Pac-Man page.

Summer Conferences

It's been a busy couple of weeks as I have been attending two scientific conferences. Last week I was at the PATAT (Practise and Theory of Automated Timetabling) conference in Belfast and I have just returned from the IEEE Conference on Computational Inetlligence in Games (CIG 2010) in Copenhagen.

Both conferences consider very different areas (not surprisingly one is about timetabling and the other is about computer games).

I'll report more on each conference in blogs in the next few days.

INFORMS 2010: Buenos Aires

I have just returned (well returning actually - I am at the airport) from the INFORMS conference in Buenos Aires. In fact, we stayed on a few days and a very good colleague of mine is Argentinian and we toured round the North of the country. The highlight, undoubtedly, being Iguazu Falls. They are spectacular (see picture for just a small part of the falls).

This is only the second INFORMS conference I have been two (the previous one was in Puerto Rico in 2007). I find them very good.
The tutorials are especially useful and the one by Mike Trick on Benders Approach for Hard Problems was particularly beneficial. At the time of writing, the powerpoint slides for this presentation we available from Mike's web site (PPTX and PPT). If I can ever get my head around the ideas underlying Bender's approach, I can see this being a very useful technique for a variety of problems.

The 2009 IEEE Symposium on Computational Intelligence and Games: Report

I have just spent the last week at the 2009 IEEE Symposium on Computation Intelligence and Games in Milan (see last post).

It has been an excellent week both from a scientific point of view and from a networking point of view (I have even added a few new facebook friends as a result of the symposium).

There really is some fantastic work going on around the world. The plenaries and tutorials showed just some of this. The work being done by people such as Ken Stanley, Michael Mateas, Yngvi Björnsson, David Stern (Microsoft Research), Stefano Lecchi (Milestone) and James Vaccaro is very impressive and the products they produce have the commercial sector (some of which work in this area anyway) really taking notice.

Of course, there is other excellent work being done, by a great many other people, and to list them all would mean listing most of the presentations given at the conference. So, although I have highlighted just a few presentations, it does not detract from all the other work being done in this area. Indeed, the newly established IEEE Transactions journal in this area is a testament to how bouyant the area is.

Another highlight at CIG'09 was the competitions. This year they really seem to have come of age. In previous years (at both CIG and other conference) the competitions were very popular, and well received, but it just has a slightly different feel this time around.

At this year's conference there were four competitions:

• Screen-Capture Ms Pac-Man. There is also a new competition where you evolve the ghosts as well as control Pac-Man being planned. This should be up and running soon.
  
• The 2K Bot Prize
  
• The Defcon AI Competition
  
• Mario AI Competition
• The Simulated Car Racing Competition

I will try and blog about each one in the future.

We hope that the presentations from the symposium will be available to view soon. They were all recorded but there are some copyright issues to resolve.

The symposium will be run again in 2010. The venue has just about been decided but it needs to be rubber stamped so I cannot say on a public forum where it will be.

The 2009 IEEE Symposium on Computational Intelligence and Games

I have just arrived in Milan for the 2009 CIG (Computational Intelligence and Games) conference. This was a conference that Simon Lucas and I started in 2005. Simon is now editor-in-chief of the IEEE Transactions on Computational Intelligence and Artificial Intelligence in Games. The 2005 conference, I believe, was partly responsible for paving the way to enabling this journal to be established. I am fortunate enough to serve as an Associate Editor for the journal.

As I said above, the first conference (actually it's a symposium, as the correct title is The IEEE Symposium on Computational Intelligence and Games) was held in 2005 in Essex (UK). The original plan was to hold the symposium every two years, but it was so successful that we decided to hold it again in 2006. This time, Sushil Louis and I chaired it. It was held at the University of Reno in Nevada.

In 2007 it was held in Hawaii, as part of the then newly formed Computational Intelligence Symposium Series of conferences (CISS). Simon, again chaired this symposium, along with Sung-Bae Cho and Alan Blair. Actually, at the 2007 CISS, I chaired the associated scheduling conference (Computational Intelligence in Scheduling (CISched).

In 2008, CIG was held in Perth, Australia, chaired by my good friends Luigi Barone and Phil Hingston.

The sympsium has now moved to Milan (chaired by Pier Luca Lanzi). It has certainly done the rounds (Essex, Reno, Hawaii, Perth and Milan) and, having been to all of them, I know from first hand experience that it is going from strength to strength.

Looking at this years program it promises to be a very interesting week. If you have an interest in computational intelligence or games, take a look at http://www.ieee-cig.org/.

MISTA Conference: Venue for 2011 announced

MISTA 2009 finished in the time honoured fashion of a social day. On this occasion it was a cruise down the River Liffey, followed by a two hour guided tour around Dublin, ending up at Trinity College Dublin (which, strangley enough is where MISTA 2009 started as it was the first place we visited when looking for a venue for the conference (in the end, we decided against TCD for various reasons)).

But, as the 2009 conference ends, planning for the 2011 conference begins.

So far, the conference has taken place in Nottingham (2003), New York (2005), Paris (2007) and Dublin (2009). At the conference banquet we announced that the 2011 conference will take place in Phoenix, Arizona. The conference will be chaired by John Fowler, Barry McCollm and myself.

Starting to plan two years in advance might seem excessive but we have found the further out you plan, the easier it is.

MISTA Conference: Plenary Talk (David Hine)

The last plenary at MISTA was given by David Hine. He is a sergeant with the Public Order Unit at New Scotland Yard (in particular Football Intelligence). His talk gave the delegates an overview of the issues and problems he faces in organising resources to police football matches in London, the wider UK and also when fans travel overseas (whether visiting other countries or fans coming to the UK).
He said that he wanted to take us into his world and also take us out of our comfort zone and he certainly did that, with some of the shocking videos that he showed. The feedback I received after his talk is captured by comments such as "an excellent presenter", "one of the best conference talks I have ever seen" and "it really brings home the impact that the schedules have on everybody's life."
I invited Dave to give the talk a few months back (after meeting up with him in London) and I would like to offer my personal thanks to him for taking a couple of days out of his busy schedule (and at the start of the football season) to give the talk to the MISTA audience.

MISTA Conference: Plenary Talk (Edmund Burke)

The MISTA conference had two plenary talks today (Raymond Kwan - see earlier blog) and Edmund Burke. Edmund's talk was entitled A Comparison of Two Methods for Reducing Take-Off Delay at London Heathrow Airport and focussed on his work (and Jason Atkin and John Greenwood) that investigates scheduling aircraft at Heathrow in preparation for take off.
The picture shows Edmund Burke (foreground) and Jacek Blazewicz (session chair).

MISTA Conference: Plenary Talk (Moshe Dror)

The MISTA conference is now well underway, after a busy morning. Our first plenary talk was by Prof. Moshe Dror (University of Arizona) and co-authored with George Steiner. His talk was entitled ‘Strong’-‘Weak’ Precedence in Scheduling: Extended Order Implications.
The picture shows Prof. Dror's talk.

MISTA Conference: Almost There

The MISTA conference is almost upon us.

It was an early start this morning (3am) in order to get to Dublin on the 06:35 flight out of East Midlands Airport. We were actually in the hotel by 09:00 and, thankfully, they had rooms ready so it was not too bad.

We spent the day getting things ready, as far as we could. The real work will start tomorrow and it looks like being a long day. I think we'll open the registration desk at 07:30 and we'll return from the Guinness Storehouse at around midnight.

In between that, we have a Plenary Talk by Moshe Dror ("‘Strong’-‘Weak’ Precedence in Scheduling: Extended Order Implications"), followed by 36 papers, split into nine sessions (the full program can be downloaded from here).

For me (and this is a personal viewpoint; not talking as the conference chair) the highlight is the Sports Scheduling session as this is a particular interest of mine, as you'll see from my previous blog postings. The papers in this session are:

• Mathematical Modeling for Maximising Gate Receipt Problem, Abdul-Hamid N.H., Kendall G. and Sagir M.
• A Heuristic for Minimizing Weighted Carry-Over Effects in Round Robin Tournaments, Guedes A.C.B. and Ribeiro C.C.
• Soccer Schedules in Europe: An Overview, Goossens D.R. and Spieksma F.C.R.
• Round-Robin Sports Scheduling from a Graph Colouring Perspective: A Case Study in Rugby Union Scheduling, Lewis R. and Thompson J.

... but there are many other excellent papers also being presented throughout the day and your preferences will depend largely on your research interests.

MISTA Conference: Program

With the MISTA conference just a week away (this time next week we'll be in the Guinness Storehouse for the reception) we have just released the scientific program.

The list of papers is available at

http://www.mistaconference.org/2009/programme/index.html

A PDF (more detailed) version can be downloaded from the same page (see the link at the top of the web page)

MISTA Conference: Proceeedings

I wonder if there is a good (and I mean simple) way to produce conference proceedings?

In a previous post, I was talking about the MISTA conference that I chair and that we were in the process of collecting all the papers and registrations. This is now done and, with the conference just a week away, we are trying to finalise the proceedings.

It could be worse. In 2003 we had hardcopy proceedings so we had to get things sorted out a lot sooner as we had to deliver the proceedings to the printers. At least, with the proceedings on CD, the timescales are not so tight and we are in charge of our own fate. On the downside you effectively have to develop another web site to enable the delegates to access the papers in a variety of ways.

But that is not the main problem (time consuming as it is). The main problem (at least for me) is three-fold

1. Ensuring that all the papers actually make it to the proceedings and that all the authors and titles are spelt correctly in the contents pages.
2. Making sure that the contents pages have the correct page numbers on (for reasons I won't go into now, it's important that we have page numbers).
3. Putting together an accurate author index so that authors can easily find their papers.

I have put together a number of conference proceedings in my time but I have never found a quick, simple and reliable of doing it, other than just taking your time and constantly checking that you have not missed anything.

Any suggestions welcome, for the next time.

Research Assessment in the UK

Like it or not the academic world is slowly (or perhaps not that slowly) moving towards being judged by how highly cited our work is. Actually, it is not a bad measure as if you publish something and nobody ever reads it, or refers to it (i.e. cites it in their own work), then was their any point in publishing that research?

The problem is, of course, that it might takes years (perhaps decades; or even more) for somebody else to recognise the value in a particular piece of research. The other problem is that once scientists know that they are being evaluated in this way, they find ways to maximise their citations (they are typically quite clever people!).

The next research assessment that will be carried out in the UK (called the Research Excellence Framework (REF)) will using citations as a major way to measure the impact of the research that is carried out by individuals, research groups and universities.

If you are interested in the REF take a look at http://www.hefce.ac.uk/Research/ref


At the moment, in the UK, this area is the subject of heated debate in the scientific community and this will be the case for the foreseeable future, especially when you bear in mind that the last research assessment (Research Assessment Exercise (RAE)) has only just been completed (the results were announced in December 2008 - http://www.rae.ac.uk).

EURO 2009 Conference

I am at the EURO conference at the moment (see http://www.euro-2009.de) (the picture was taken during the opening ceremony).

This is an annual conference for the European Operational Research Societies. This year it has attracted around 2000 delegates, which was a lot more than we had expected (I know as I am on the main Program Committee and have been actively involved in planning and organising the conference, although I have not worked anything like as hard as some people I could mention - but won't mention them by name for fear of embarassing them).

As the conference progresses I'lll report on anything that grabs my interest/attention.

MISTA Conference

Since 2003 I have chaired the Multidiscplinary Conference on Scheduling: Theory and Applications (MISTA). The first conference (2003) was held in Nottingham, the second (2005) was held in New York and the third conference (2007) took place in Paris.

The 2009 conference (the 4th in the series) is due to take place in Dublin (10th - 12th August 2009).

The conference is now only about eight weeks away and, as anybody knows who has organised a conference, it is a busy time for all concerned (both organisers and authors).

Our main efforts at the moment are being directed at ensuring that revised papers (taking into account the comments of the reviewers) have been uploaded and checking that each paper has an registered author.

Once we have registration/paper uploads resolved (in the next few days we hope), we will close the web site (we are using easychair) so that nobody tries to "sneak" in a late paper.

Then the task of producing the proceedings begins. This has to be done with great care as just a single mistake will haunt us forever.