Blog moved

I have decided to move this blog to my own domain. All the old posts will be there, along with any future posts.

You can find the new blog at:

http://graham-kendall.com/blog/

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.

SlideShare

It was only recently that I came across slideshare. It is one of those ideas (I suppose a bit like YouTube) that you have heard about, but you don't really know how useful it is until you have used it.
In essence, slideshare is a very simple concept (like most of the very succesful internet applications). It enables people to upload presentations that other people can access.
Like YouTube and Wikipedia you can spend a lot of time looking at subjects that you never really thought you had an interest in. It is also a convinient place to store your own presentations in case your laptop crashes, your USB breaks etc. etc.
So far, I have only uploaded a couple of presentations but I hope to add to that in the near future.

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.

Geocoding: Trials and Tribulations

For the past few months I have had a small project on the back burner to try and make geocoding easier.

The motivation can be traced back to the data collection I had to do for the data I needed for my research on minimising the amount of travelling that football supporters have to do over the Christmas holiday period (if you are interested in this see this link).

When I collected the original data I used greenflag.com. I could have used theaa.com or rac.co.uk. The problem with the latter two is that you had to type in the to/from postcode into a web form. At least with greenflag.com the postcodes were part of the URL so it was a simple case of generating the correct URLs (which I did with Excel), uploading to a web site and then clicking on each link.

But this was a long winded process in that I had to a) click on every to/from link (about 900) and then scroll the screen to collect the actual mileage. That takes a long time and as I have done this for seven seasons I thought it was about time to try and automate the process.

The obvious candidate was to use Google maps. When I started the sports scheduling research Google maps did not provide the facilities that I required. Things have moved on since then and Google maps now has an API which makes this type of automation a possibility.

So, over the last few months I have been investigating how to use Google maps, which does not come without its problems. For example, it is not that accurate when using UK postcodes, you have to learn the API, ideally you need to geocode UK postcodes to longitude and latitude etc.

I think that I have now resolved most of these problems and am just doing the last stages of test. So, more soon.

Vehicle Routing Datasets

For reasons which will become apparent in the fullness of time I have recently been trying to track down all the vehicle routing datasets that are out there; specifically the Capacitated Vehicle Routing Problem (CVRP).

I know that the problem was introduced in 1959 (with small instances being made available in that paper¹) and I think I have tracked down the majority of datasets since then, but if anybody out there has a list (or a reference to a list) it would be helpful.


¹ Dantzig, G.B., Ramser, J.H., 1959. The truck dispatching problem. Management Science 6, 80–91

Conjuring Trick: Revealed

Thank you for all the feedback to my last blog, both personally and through facebook.

The answer is that information is communicated via the four remaining cards. It is not obvious how it is done but take a look at the article by Colm Mulcahy, which explains all.

If you are interested in these sort of puzzles I fond this one at Gurmeet Singh's blog. It is an excellent blog and contains many other puzzles like this.

Conjuring Trick

I recently came across another blog (I'll point you to that blog at a later date), which has a number of puzzles on it. One, in particular caught my eye (probably because of a long time fascination with conjuring).

The trick works as follows.

A volunteer chooses five cards from a normal pack of cards. You take the five cards, look at them and return one of the cards to the volunteer. The other four cards are handed to another volunteer. You leave the room and a colleague enters. The second volunteer reads out the cards you gave them and your colleague names the card that the first volunteer is holding.

How is this done (post your ideas)?

If you want to know, click the "interesting" box at the bottom of this blog and, if there is enough interest, I'll point you to the original blog and the answer (unless somebody already knows, of course).