In this post I want to talk briefly about some work I’ve been doing writing a visualisation system for the research I’m undertaking. In a mad moment of satisfaction I posted a screenshot of it to Twitter, and it generated enough interest that it seemed worth a wee explanation.

Background

In Automated Planning we typically describe the environment we want to work with in a language called PDDL – the Planning Domain Description Language. This has three principal components :

1. A list of the possible actions that you can undertake in the world, the facts that have to be true before the action can be undertaken and the way the action changes the world.
2. A complete listing of all the facts that are true in the world initial.
3. A list of the important facts that must hold true for the task to have been satisfied.

Typically this is split into two parts, a “Domain” description, and a “Problem” description. This might give you a domain that says there are trucks, planes, packages and locations and you can move the planes and the trucks between locations and load and unload the packages onto trucks or planes. That might look something a little like this. Then you have a problem file and that tells you how many of each different thing you have and how everything is linked together.

So far so good.

A Reformulation

The problem is that all of these facts that can be true or false is pretty miserable, and for reasons that I’ll get into in another post sometime, what is really needed is a different kind of representation, one that has replaces high number of variables with a low number of possible values (in this case two) for a low number of variables with a higher number of possible values. It turns out that you can do the translation between the two automatically, and what you get is a long-ass file that really is next to unintelligible if an actual person reads it. Which sort of sucks, since a lot of this stuff needs to be debugged in the model to verify that the information being fed into the AI system makes sense.

Not only that, but the way I’m working with these graphs means that I want to track which variable has what value currently, what value it needs to take in the goal state and how the values can change within a single variable. Previously that has meant reading a _lot_ of command line output and getting pretty good at parsing a lot of data on the fly – as well as spending a lot of time going through the output looking to see where the system went haywire.

Sample DTG for a single Truck object

More Complex Example for a Package Object

Visualisation’s what you need (if you want to be a record breaker)

So the obvious solution has been to develop a visualisation system. It turns out that this isn’t _so_ straightforward, as it means writing a GUI algorithm that can take any kind of graph description and turn into a representation that can be displayed in an application and updated on the fly. Arranging a graph of unknown size and connectivity on the fly is a difficult problem it turns out, and inevitably, the old stalwart dot (or more accurately his cousin Circo) has been employed to enhance it. The upshot of this system is that I can take a PDDL representation of a problem, translate it into SAS+ using a slightly modified version of Helmert’s script, parse that into the formalism used by my Integrated Influence Architecture, load it into the architecture and get a nice pictorial representation of what exactly is happening in the guts of the thing, and how the world my agent is operating in is actually put together. This makes debugging your models a lot easier since you can actually see the operators and transitions in front of you

Colourisation

One final note is on the colouring of the nodes within the graph – this is part of the architecture that I mentioned above and represents the result of applying a “clustering” algorithm to the graph. Essentially it is a load of fancy maths which boils down to grouping nodes that are close together, the idea being that then the AI system can focus on traversing between the clusters, which will save quite a bit of computation micro-managing how it moves within specific clusters of a graph, thus breaking a problem into essentially “bite-sized chunks”. You can read more about this in the paper detailing the process which will be presented next week at the International Conference on Intelligent Data Engineering and Automated Learning.

Clustering of Package DTG

Comments, questions and criticisms are more than welcome in the comments – obviously this isn’t groundbreaking stuff but I’m pretty chuffed with it and with a bit of luck it will be of real use to me. If anyone wants the source, they’re welcome to it, but as it relies extensively on having the right python libs in exactly the right place and other hackery, I’m not at this moment going to put it out there for absolutely everyone to grab and them mail me that it doesn’t work – it’s awful hacky, so if you do want a copy, be warned!

Finally finally finally, I’d be remiss if I didn’t explicitly thank the following folk for their contributions : Malte Helmert for writing the original PDDL -> SAS+ translator, Christian Muise for the KRToolkit and extensive Python support and AT&T Labs for the GraphViz toolkit and the Grappa Java library

I was about four or five when I got my first computer – a Spectrum ZX something-or-other and I know that it had a darts game based on the old UK game show Bullseye using the light gun and a Thundercats game, though I can’t really remember what else or what I played first. That packed in pretty quickly – well within warranty – and ended up being exchanged (after a couple of defective Spectrums) for an Atari ST that I’ve still got somewhere along with a pile of games far too long to list. Someday it will be a collectors item – along with every other one in people’s attics waiting for that day

In terms of modern-ish gaming, the first game I ever got on the PC (a powerhouse 75MHz Pentium) was Wing Commander 3, and I’ve still got it on my bookcase. I’d played the first one extensively on my dad’s office 286 and was very hooked on the whole Wing Commander universe (still am to an extent, I even watched the film and own the novelisation of the film!).

The real problem I have with answering the question directly (rather than waffling ) is that I’ve no real idea what "The First Game I Ever Played" was. I’ve been gaming now for longer than I’ve got coherent memories so figuring out what the first one was is awful tricky. These are the "formative" moments from my video game upbringing though, so decide which one counts as the "first" for yourself

Ask me anything

Here’s what a Double Down is : 2 pieces of chicken with a coating (more or less Crispy Strips for those who know their KFC too well) with some faux-bacon, faux-cheese and mayo in the middle. It’s not disgusting, it isn’t nice, it isn’t even that tasty. It’s basically a shock tactic to make people think it is the grossest thing ever and generate some press attention, whilst at the same time being tame and boring. A normal serving of their crispy strips is a pack of three so by its nature, regardless of the presentation technique, two is less disgusting than three.

So yeah, I’m incredibly disappointed. I didn’t throw up, I didn’t have a heart attack and I’ve got no interest in having another one – it’s just media hype. Congratulations KFC, you managed to Quentin Tarantino the junk food industry.

And let’s not even start on this bullshit that KFC don’t serve fries anymore. Potato wedges? Are you fucking kidding me?

• My latest article for AIGameDev.com has been returned to me for editing, and I’ve not got that done yet.
• I have not yet put together a new theme for @CristinaSR’s new website
• I have not yet finished writing my paper for “the 11th International Conference on Intelligent Data Engineering and Automated Learning”
• I have not had chance to get a poster put together for SICSA2010 yet
• I have not written copy for another website I am helping to develop for another friend

On the other hand, I have got some feedback on last week’s lecture to the British Computing Society. @DLivingstone is one of the committee members for the Glasgow branch of the BCS and forwarded the results of a SurveyMonkey poll they conducted after the event. I’m going to extract the two most relevant questions to me and showcase the results :

Q. How did you rate the quality of the event (e.g. Presentation / Speaker etc.) ?

1. Excellent – 53,8%
2. Good – 38.5%
3. Acceptable – 7.7%
4. Poor – 0%

Q. Reason for [answer to previous question in which 100% of responders claimed to have enjoyed the event]

• Presenter (Luke) was very knowledgeable and engaging. Good use of humour and an obvious passion for the subject.
• Refreshing knowledge and pointer to new developments, enthusiastic speaker
• Good well informed, enthusiastic [sic] quality presentation
• I have done some reading on the subject in my time and it was good to hear of the latest in the field
• Excellent speaker, interesting topic and good demo.
• Prior knowledge of some of the subject matter. Very good to see how some studies have progressed
• Gaming was a new concept for me, was interesting to note how biological concepts and physics are put into software development
• A good general introduction to the subject for the non-specialist.
• Informative and interesting

I am absolutely thrilled by this. I can’t tell you how pleased I am, and I’m delighted that people enjoyed sitting and listening as much as I enjoyed standing and talking! I will be working my way through my giant to-do list as quick as I can, and once that is done, expect those posts that I’ve promised to appear here.

• The Conservatives are putting “family values” front and center, and whilst I can get behind their policies on a lot of things, I’m not prepared to acknowledge the philosophy that says that the only valid family unit is a male and female who have signed a religious contract.
• Labour. Well, that says it all really. The last 13 years stand as a testament to their incompetence. It seems like they won’t be happy until they’ve taxed-and-spent the ambition out of anyone trying to be successful in the UK, and as a smart very well educated guy with a bright future, from a reasonably well off family, that offends me right in my very soul.
• Liberal Democrats are the obvious remaining choice, though I have two bones to pick with them. Firstly, the incumbent candidate in my area is LibDem Alan Reid MP. I got a nice email from Alan on Easter Monday, sharing my concerns about the Digital Economy Bill and expressing a similar disgust. Except Alan Reid MP didn’t care enough to actually show up and vote against it, which put a very big mark against him in my book. The second problem I have is that I received a letter from Nick Clegg himself this morning which among other things pointed out that the Conservatives were bank rolled by Lord Ashcroft, so no wonder they wanted tax breaks for millionaires. Two things – firstly Helensburgh (where I live) is a very affluent area. I’ve heard people say that Helensburgh has the most millionaires per capita than any other town, though I find this somewhat hard to believe and have never been able to substantiate it. But if it isn’t true exactly, then the sentiment is – we’re a wealthy well-to-do town, so calling out millionaires here probably isn’t going to play well. Secondly, let’s put things into perspective here – Ashcroft isn’t a millionaire, Ashcroft is a billionaire. With a ‘b’. That’s a 1,000 times difference. That’s like taking a shot at actual millionaires by claiming anyone with £1,000 in the bank is evil – it’s orders of magnitude out. So either there’ a fairly blatant bait-and-switch going on in the LibDem literature, or Nick Clegg can’t tell the difference between a ‘b’ and an ‘m’ and neither of those fun facts makes for a palatable Prime Minister.
• Of course, in my area, I’d probably get sued by Alex Salmond if I didn’t also highlight that I could vote for the SNP. But I’ve had neither enough Buckfast, Irn Bru and Deep Fried Mars Bar, nor watched Braveheart back to back enough times for that to seem like anything but a pointless waste of time. It’s worth noting that Sean Connery, the poster boy of the SNP and one of the strongest advocates of Scottish independence, doesn’t actually live in the UK…

My point is that this isn’t a political blog, my recap of why the options boil down to selecting the lesser of four douchebags notwithstanding. So you might ask, why am I questioning why I get up in a morning. It’s this – it has taken me just a half hour to write this post. At ten this evening, my creative juices are flowing, my writing is in full swing and I’m bashing out words as fast as my fingers will move. Contrast this with this morning’s effort where I struggled to wring 200 words out of myself. I think increasingly I need to accept that as far as being creative and particularly writing, I’m very much a night-owl. I’m also very motivated by deadlines – I think they focus the mind a lot more and give you a sense of urgency that you just don’t get otherwise. And that’s why I don’t know why I bother getting up in a morning. I might as well stay in bed – I’ll get the same amount done because really I should only be eating into my recreation time. My work time maybe shouldn’t start until later in the day. It would certainly feel a lot less frustrating that sitting in front of my laptop all day and achieving a total of 200 words for hours of effort :s

Edit : This post really was only meant to cover the last paragraph. Went very far off message there somewhere :s

Firstly, I’m trying to get the new “@Anywhere” system from Twitter integrated to the site this morning. This should mean that Twitter names will now auto-link and show Hovercards when I reference them in the text. Hat tip to @Boagworld for the link.

Since I’m doing a quick post of Twitter people, I’d also like to quickly shout to @MituK for recommending “Killer Game Programming in Java” to me. A weighty tome with almost a full thousand pages, I’m slowly working my way through it.

Finally, the BCS lecture on Monday went really well. I’ve put the slides up on Slideshare, though as I have been doing previously, I will post a separate update and embed them here. I had a lot of fun doing it, and there were some really interesting questions which I will be trying to find time to turn into actual posts here on the site shortly.

I’ve been asked to give a lecture to the Glasgow branch of the British Computing Society on Monday. Its very short notice as the speaker they had lined up – Dr. Darryl Charles – has had to pull out at the last minute. The subject is “AI in Video Games” which makes it right in my ballpark so I have of course agreed to fill in, but both the honour of being asked to fill these rather large shoes, and the intimidation of presenting for the BCS are both a little overwhelming. And of course I need to actually have a presentation by Monday (and my OCD is preventing me from just recycling an old one…).

Presenting at the Glasgow BCS might not be the Royal Society Christmas lectures, but it is by far the biggest gig I’ve had to date – it was only in December of last year (or four months ago) that I did my first research presentation outside of my own department, and my second and third were about a month ago today. Of course, my time as a consultant has been incredibly useful in terms of my comfort with public speaking – particularly on topics I do know about. Even given that experience, I’m still a little nervous about this one, but more than anything I’m so pleased at being given the opportunity to talk about my passion with a new audience.

If you are in the Glasgow area, I’ll be speaking at 1830 on Monday 12th April in the Lord Todd building of the University of Strathclyde. I believe that doors open at 1800 for some snacks. You can find more information here – please come along and hear me ramble!

I wrote to Harriet Harman as part of the 38Degrees campaign to contact her directly and appeal to her sense of decency (bit of a wasted effort…). I haven’t seen a vast number of people talking about having received a response. I did note from the reply that they made a point of referencing my qualifications (because I was feeling like enough of a cock to use the full line of letters after my name : Luke Dicken MRes(Dist) MSc BSc(Hons) for those keeping track in the cheap seats), though I’m not sure if that is the reason I got a reply where others seem not to have, or if it is just that I’m one of the few people who bothered to take a letter that was basically content-free and spin-tastic seriously, but for those who care, for those who were asking, here is the text of the response.

I’ve had enough to drink and enough of the bullshit and lies that I decided to have a bit of fun with this one, and whilst I accept that a reply to a form letter almost certainly ends up in the kind of blackhole that no email has ever escaped from, I wrote one anyway :

Yeah well. We’ll see what happens. I’m not holding my fucking breath…

In February, Luke Dicken, one of our Ph.D. students was able to spend a week at Rockstar North, the Edinburgh-based developer behind the highly successful “Grand Theft Auto” series of video games.

Luke’s research focuses primarily on developing Artificial Intelligence in the context of video games, so this was a very good opportunity to get a closer look at how the industry works from a ground level and a better understanding of exactly how the development process works.

During his week at Rockstar, Luke was working as a “Focus Tester”, which means that he was expected to sit down and play a game from start to finish, noting a not only any bugs encountered but also more generally the difficulty and overall feel of the game. Focus Testing is analogous to the more traditional market research technique of “Focus groups”, but rather than a group of people being selected to be surveyed, the group instead plays the game and gives feedback. From a technical point of view, these people do not generally add much except another set of eyes looking for problems in the game, and without detailed understanding of the mechanics of the underlying code even the most skilled of tester cannot hope to diagnose these flaws.

However, by the time a game nears completion, the in-house test team will have played it over and over in many different versions, making them far too close to the project to judge the broader game behind the sequence of individual sections that have been tested to death. This is the key role that the Focus Tester can fill – by picking up the game and playing with no real knowledge of it, they provide a reasonably good perspective on issues such as game difficulty, a very hard aspect for an internal testing team to pin down, given their level of familiarity and expertise at playing the game. Similarly, Focus Testers can also get a better sense for the flow of the game and the overall experience it provides as an entire unit, and can provide valuable feedback that makes for a stronger product when it is released.

Overall, Luke gained some important insights into the workings of the game industry and as a result has a better perspective on the context in which his work with AI will be applied once it is complete, as well as developing contacts within the industry.

I would however urge you to check out the original article here as webmaster extraordinaire Paul Smith has created a very fancy graphic to accompany it.