Tantrix: P=NP?

You can find computer science everywhere – even in popular Solitaire games and puzzles. Most people have played games like Tetris, Battleships, Mastermind, Tantrix and Minesweeper at some point. In fact, all these games have a link to one of the deepest, fundamental problems remaining in Computer Science. They are all linked to a famous equation that is to do with the ultimate limitations of computers.

A 5 tile Tantrix puzzle to solve

The sciences have many iconic equations that represent something fundamental about the world. The most famous is of course Einstein’s E=mc², which even non-scientists have heard of. The most famous equation in computer science is ‘P=NP’. The only trouble is no one has yet proved whether it is true or not! There is even a million dollar prize up for grabs for anyone who does, not to mention great fame!

P=NP boils down to the difference between checking if someone’s answer to a puzzle is correct, as against having to come up with the answer in the first place.

You are so NP!

Computer Scientists call problems where it is easy to check answers ‘NP problems’. Ones where it’s also easy to come up with solutions are ‘P problems’. So P=NP, if it were true, would just mean that all problems that are easy to check are also easy to solve.

Let’s take Tantrix rotation puzzles to see what it is all about. Tantrix is a popular domino-type game using coloured hexagonal pieces like the ones in the image. The idea of a Tantrix rotation puzzle is that you place some tiles randomly on the table in a connected pattern. You are then not allowed to move the position of any piece. All you can do is rotate them on the spot. The problem is to rotate the pieces so that all the coloured lines match where tiles meet – red to red lines, blue to blue lines and so on.

Have a go at the Tantrix rotation puzzle above before you read on.

Easy to check?

A solution is here if you want to check it. In fact you can quickly check any claimed rotation puzzle ‘solution’. All you do (the checking ‘algorithm’) is look at each tile in turn and check each of its edges does match the edge of the tile it touches, if any. If you find a tile edge that doesn’t match then the ‘solution’ isn’t a solution after all. How long would that take to check? With say a 10 piece puzzle there are 10 pieces to check each with 6 edges so in total that is 10×6 = 60 things to check. That wouldn’t take too long. Even with 100 pieces it would be only 600 things to check – 10 minutes if you could check an edge a second. So Tantrix rotation puzzles are NP puzzles – they can be checked quickly.

But can you solve it?

The question is: “Are rotation puzzles P puzzles too?” Can they always be solved quickly if you or a computer were clever enough? You may have found that puzzle easy to solve. It is much harder to come up with a quick way that is guaranteed to solve any rotation puzzle I give you. One way would be to methodically work through every combination of tile rotations to see if it worked. That would take a long time though.

There are 6 positions for the first piece (ways to rotate it), but for each of those 6 positions the second piece could be in 6 positions too … and so on for each other piece. Altogether for a 10-tile puzzle there are 6x6x6x6x6x6x6x6x6x6 (i.e., over 60 million) positions to check looking for a solution (and we might have to check them all). If you could check one position a second, it would take you around 700 days non-stop (no eating or sleeping). That is just for a 10-tile puzzle…now for a 100-tile puzzle – I’ll leave you to work out how long that would take.

It is not what computer scientists call “quick”.

How clever do you have to be?

If P=NP is true it would mean there is a quick way of solving all Tantrix rotation puzzles out there, if only someone were clever enough to think of it. If P=NP is not true then it might just not be possible however clever you are. Trouble is no-one knows if it’s true or not…

Tantrix: Solve one, solve them all

We’ve seen how Tantrix rotation puzzles can show what we mean by the question “Is P=NP?” It turns out Tantrix rotation puzzles are also something called ‘NP-complete’. That means it is one of a special kind of problem.

NP-complete problems are the really hard ones. Some are also really important to be able to solve quickly. For example, suppose you are a taxi driver and wanted your SatNav to be able to quickly work out the fastest circular route that went via a whole series of places you wanted to visit (in any order), getting you back home. Simple as it sounds, it is an NP-complete problem. It can’t be done quickly even by a fast computer. The best that can be done is to come up with a good answer not a perfect one – using what’s known as a ‘heuristic’. There are lots of ways of coming up with such good answers – using Swarm Intelligence is one way, for example. The point is none can guarantee the best answer every time.

NP-completeness is important because if you could come up with a quick algorithm for solving one NP-complete problem, computer scientists know how to convert such an algorithm into one that solves all the other NP problems…P would equal NP…Trouble is no one has so far done it…

Paul Curzon, Queen Mary University of London, 2007

Play Tantrix online at the official site.

Emoticons and Emotions

Emoticons are a simple and easily understandable way to express emotions in writing using letters and punctuation without any special pictures, but why might Japanese emoticons be better than western ones? And can we really trust expressions to tell us about emotions anyway?

African woman smiling 
Image by Tri Le from Pixabay

The trouble with early online message board messages, email and text messages was that it was always more difficult to express subtleties, including intended emotions, than if talking to someone face to face. Jokes were often assumed to be serious and flame wars were the result. So when in 1982 Carnegie Mellon Professor Scott Fahlman suggested the use of the smiley : – ) to indicate a joke in message board messages, a step forward in global peace was probably made. He also suggested that since posts more often than not seemed to be intended as jokes then a sad face : – ( would be more useful to explicitly indicate anything that wasn’t a joke.

He wasn’t actually the first to use punctuation characters to indicate emotions though. The earliest apparently recorded use is in a poem in 1648 by Robert Herrick, an English poet in his poem “To Fortune”.

Tumble me down, and I will sit
Upon my ruins, (smiling yet:)

Whether this was intentional or not is disputed, as punctuation wasn’t consistently used then. Perhaps the poet intended it, perhaps it was just a coincidentall printing error, or perhaps it was a joke inserted by the printers. Either way it is certainly an appropriate use (why not write your own emoticon poem!)

You might think that everyone uses the same emoticons you are familiar with but different cultures use them in different ways. Westerners follow Fahlman’s suggestion putting them on their side. In Japan by contrast they sit the right way up and crucially the emotion is all in the eyes not the mouth which is represented by an underscore. In this style, happiness can be given by (^_^) and T or ; as an indication of crying, can be used for sadness: (T_T) or (;_;). In South Korea, the Korean alphabet is used so a different character set of letter are available (though their symbols are the right way up as with the Japanese version).

Automatically understanding people’s emotions is an important area of research, called sentiment analysis, whether analysing text, faces or other aspects that can be captured. It is amongst other things important for marketeers and advertisers to work out whether people like their products or what issues matter most to people in elections, so it is big business. Anyone who truly cracks it will be rich.

So in reality is the western version or the Eastern version more accurate: are emotions better detected in the shape of the mouth or the eyes? With a smile at least, it turns out that the eyes really give away whether someone is happy or not, not the mouth. When people put on a fake smile their mouth does curve just as with a natural smile. The difference between fake and genuine smiles that really shows if the person is happy is in the eyes. A genuine smile is called a Duchenne smile after Duchenne de Boulogne who in 1862 showed that when people find something actually funny the smile affects the muscles in their eyes. It causes a tell-tale crow’s foot pattern in the skin at the sides of the eyes. Some people can fake a Duchenne too though, so even that is not totally reliable.

As emoticons hint, because emotions are indicated in the eyes as much as in the mouth, sentiment analysis of emotions based on faces needs to focus on the whole face, not just the mouth. However, all may not be what it seems as other research shows that most of the time people do not actually smile at all when genuinely happy. Just like emoticons facial expressions are just a way we tell other people what we want them to think our emotions are, not necessarily our actual emotions. Expressions are not a window into our souls, but a pragmatic way to communicate important information. They probably evolved for the same reason emoticons were invented, to avoid pointless fights. Researchers trying to create software that works out what we really feel, may have their work cut out if their life’s work is to make them genuinely happy.

     ( O . O )
         0

– Paul Curzon, Queen Mary University of London, Summer 2021

Knitters and Coders: separated at birth?

People often say that computers are all around us, but you could still escape your phone and iPod and go out to the park, far away from the nearest circuit board if you wanted to. It’s a lot more difficult to get away from the clutches of computation itself though. For one thing, you’d have to leave your clothes at home. Queen Mary Electronic Engineer Karen Shoop tells us about the code hidden in knitting, and what might happen when computers learn to read it.

Boy with wool hat and jumper on snowy day

If you’re wearing something knitted look closely at it (if it’s a sunny day then put this article away till it gets colder). Notice how the two sides don’t look the same: some parts look like a raised ‘v’ and others like a wave pattern. These are made by the two knitting stitches: knit and purl. With knit you stick the needle through and then behind the knitting; with purl you stick the needle in the other direction, starting behind the knitting and then pointing at the knitter. Expert knitters know that there’s more to knitting than just these two stitches, but we’ll stick to knit and purl. As these stitches are combined, the wool is transformed from a series of waves or ‘v’s into a range of patterns: stretchy stripes (ribs), raised speckles (moss), knots and ropes (cable). It all depends on the number of purls and knits, how they are placed next to each other and how often things are repeated.

Knitters get very proficient at reading knitting patterns, which are just varying combinations of k (knits) and p (purls). So the simplest pattern of all, knitting a square, would look something like:

’30k (30 knit stitches), finish the line, then repeat this 20 times’.

A rib would look like: ‘5k, 5p, then repeat this [a certain number of times], then repeat the line [another number of times]’

To a computer scientist or electronic engineer all this looks rather like computer code or, to be precise, like the way of describing a pattern as a computer program.

How your jumper is like coding

So look again at your knitted hat/jumper/cardi and follow the pattern, seeing how it changes horizontally and vertically. Just as knitters give instructions for this in their knitting pattern, coders do the same when writing computer programs. Specifically programmers use things called regular expressions. They are just a standard way to describe patterns. For example a regular expression might be used to describe what an email address should look like (specifying rules such as that it has one ‘@’ character in the middle of other characters, no full-stops/periods immediately before the @ and so on), what a phone number looks like (digits/numbers, no letters, possibly brackets or hyphens) and now what a knitting pattern looks like (lots of ks and ps). Regular expressions use a special notation to precisely describe what must be included, what might possibly be included, what cannot be, and how many times things should be repeated. If you were going to teach a computer how to read knitting patterns, a regular expression would be just what you need.

Knitting a regular expression

Let’s look at how to write a knitting pattern as a regular expression. Let’s take moss or seed stitch as our example. It repeats a “knit one purl one” pattern for one line. The next line then repeats a “purl one knit one” pattern, so that every knit stitch has a purl beneath it and vice versa. These two lines are repeated for as long as is necessary. How might we write that both concisely and precisely so there is no room for doubt?

In knitting notation (assuming an even number of stitches) it looks like: Row 1: *k1, p1; rep from * Rows 2: *p1, k1; rep from * or Row 1: (K1, P1) rep to end Row 2: (P1, K1) rep to end Repeat these 2 rows for length desired.

piles of woollen clothes

All this is fine … if it’s being read by a human, but to write experimental knitting software the knitting notation we have to use a notation a computer can easily follow: regular expressions fit the bill. Computers do not understand the words we used in our explanation above: words like ‘row’, ‘repeat’, ‘rep’, ‘to’, ‘from’, ‘end’, ‘length’ and ‘desired’, for example. We could either write a program that makes sense of what it all means for the computer, or we could just write knitting patterns for computers in a language they can already do something with: regular expressions. If we wanted to convert from human knitting patterns to regular expressions we would then write a program called a compiler (see Smart translation) that just did the translation.

In a regular expression to give a series of actions we just name them. So kp is the regular expression for one knit stitch followed immediately by one purl. The knitting pattern would then say repeat or rep. In a regular expression we group actions that need to be repeated inside curved brackets, resulting in (kp). To say how many times we need to repeat, curly brackets are used, so kp repeated 10 times looks like this: (kp){10}.

Since the word ‘row’ is not a standard coding word we then use a special character, written, \n, to indicate that a new line (=row) has to start. The full regular expression for the row is then (kp){10}\n. Since the first line was made of kps the following line must be pks, or (pk){10}\n

These two lines have to be repeated a certain number of times themselves, say 20, so they are in turn wrapped up in yet more brackets, producing: ((kp){10}\n(pk){10}\n){20}.

If we want to provide a more general pattern, not fixing the number of kps in a row or the number of rows, the 10 and 20 can be replaced with what are called variables – x and y. They can each stand for any number, so the final regular expression is:

((kp){x}\n(pk){x}\n){y}

How would you describe a rib as a regular expression (remember, that’s the pattern that looks like stretchy stripes)? The regular expression would be ((kp){x}\n){y}.

Regular expressions end up saying exactly the same thing as the standard knitting patterns, but more precisely so that they cannot be misunderstood. Describing knitting patterns in computer code is only the start, though. We can use this to write code that makes new patterns, to find established ones or to alter patterns, like you’d need to do if you were using thicker wool, for example. An undergraduate student at Queen Mary, Hailun Li, who likes knitting, used her knowledge to write an experimental knitting application that lets users enter their own combination of ps and ks and find out what their pattern looks like. She took her hobby and saw how it related to computing.

Look at your woolly jumper again…it’s full of computation!

– Karen Shoop, Queen Mary University of London, Summer 2014

Die another Day? Or How Madonna crashed the Internet

A lone mike under bright stage lights

From the cs4fn archive …

When pop star Madonna took to the stage at Brixton Academy in 2001 for a rare appearance she made Internet history and caused more that a little Internet misery. Her concert performance was webcast; that is it was broadcast real time over the Internet. A record-breaking audience of 9 million tuned in, and that’s where the trouble started…

The Internet’s early career

The Internet started its career as a way of sending text messages between military bases. What was important was that the message got through, even if parts of the network were damaged say, during times of war. The vision was to build a communications system that could not fail; even if individual computers did, the Internet would never crash. The text messages were split up into tiny packets of information and each of these was sent with an address and their position in the message over the wire. Going via a series of computer links it reached its destination a bit like someone sending a car home bit by bit through the post and then rebuilding it. Because it’s split up the different bits can go by different routes.

Express yourself (but be polite please)

To send all these bits of information a set of protocols (ways of communicating between the computers making up the Internet) were devised. When passing on a packet of information the sending machine first asks the receiving machine if it is both there and ready. If it replies yes then the packet is sent. Then, being a polite protocol, the sender asks the receiver if the packets all arrived safely. This way, with the right address, the packets can find the best way to go from A to B. If on the way some of the links in the chain are damaged and don’t reply, the messages can be sent by a different route. Similarly if some of the packets gets lost in transit between links and need to be resent, or packets are delayed in being sent because they have to go by a round about route, the protocol can work round it. It’s just a matter of time before all the packets arrive at the final destination and can be put back in order. With text the time taken to get there doesn’t really matter that much.

The Internet gets into the groove

The problem with live pop videos, like a Madonna concert, is that it’s no use if the last part of the song arrives first, or you have to wait half an hour for the middle chorus to turn up, or the last word in a sentence vanishes. It needs to all arrive in real time. After all, that is how it’s being sung. So to make web casting work there needs to be something different, a new way of sending the packets. It needs to be fast and it needs to deal with lots more packets as video images carry a gigantic amount of data. The solution is to add something new to the Internet, called an overlay network. This sits on top of the normal wiring but behaves very differently.

The Internet turns rock and roll rebel

So the new real time transmission protocol gets a bit rock and roll, and stops being quite so polite. It takes the packets and throws them quickly onto the Internet. If the receiver catches them, fine. If it doesn’t, then so what? The sender is too busy to check like in the old days. It has to keep up with the music! If the packets are kept small, an odd one lost won’t be missed. This overlay network called the Mbone, lets people tune into the transmissions like a TV station. All these packages are being thrown around and if you want to you can join in and pick them up.

Crazy for you

Like dozens of cars

all racing to get through

a tunnel there were traffic jams.

It was Internet gridlock.

The Madonna webcast was one of the first real tests of this new type of approach. She had millions of eager fans, but it was early days for the technology. Most people watching had slow dial-up modems rather than broadband. Also the number of computers making up the links in the Internet were small and of limited power. As more and more people tuned in to watch, more and more packets needed to be sent and more and more of the links started to clog up. Like dozens of cars all racing to get through a tunnel there were traffic jams. Packets that couldn’t get through tried to find other routes to their destination … which also ended up blocked. If they did finally arrive they couldn’t get through onto the viewers PC as the connection was slow, and if they did, very many were too late to be of any use. It was Internet gridlock.

Who’s that girl?

Viewers suffered as the pictures and sound cut in and out. Pictures froze then jumped. Packets arrived well after their use by date, meaning earlier images had been shown missing bits and looking fuzzy. You couldn’t even recognise Madonna on stage. Some researchers found that packets had, for example, passed over seven different networks to reach a PC in a hotel just four miles away. The packets had taken the scenic route round the world, and arrived too late for the party. It wasn’t only the Madonna fans who suffered. The broadcast made use of the underlying wiring of the Internet and it had filled up with millions of frantic Madonna packets. Anyone else trying to use the Internet at the time discovered that it had virtually ground to a halt and was useless. Madonna’s fans had effectively crashed the Internet!

Webcasts in Vogue

Today’s webcasts have moved on tremendously using the lessons learned from the early days of the Madonna Internet crash. Today video is very much a part of the Internet’s day-to-day duties: the speed of the computer links of the Internet and their processing power has increased massively; more homes have broadband so the packets can get to your PC faster; satellite uplinks now allow the network to identify where the traffic jams are and route the data up and over them; extra links are put into the Internet to switch on at busy times; there are now techniques to unnoticeably compress videos down to small numbers of packets, and intelligent algorithms have been developed to reroute data effectively round blocks. We can also now combine the information flowing to the viewers with information coming back from them so allowing interactive webcasts. With the advent of digital television this service is now in our homes and not just on our PC’s.

Living in a material world

It’s because of thousands of scientists working on new and improved technology and software that we can now watch as the housemate’s antics stream live from the Big Brother house, vote from our armchair for our favourite talent show contestant or ‘press red’ and listen to the director’s commentary as we watch our favourite TV show. Like water and electricity the Internet is now an accepted part of our lives. However, as we come up with even more popular TV shows and concerts, strive to improve the quality of sound and pictures, more people upgrade to broadband and more and more video information floods the Internet … will the Internet Die another Day?

Peter W. McOwan and Paul Curzon, Queen Mary University of London, 2006

Read more about women in computing in the cs4fn special issue “The Woman are Here”.

The Emoji Crystal Ball

Fairground fortune tellers claim to be able to tell a lot about you by staring into a crystal ball. They could tell far more about you (that wasn’t made up) by staring at your public social media profile. Even your use of emojis alone gives away something of who you are.

Reflective ball with dots of lights
Image by Hier und jetzt endet leider meine Reise auf Pixabay  from Pixabay

Walid Magdy’s research team at Edinburgh University are interested in how much people unknowingly give away about themselves when they use social media. They have found that it’s possible to work out an awful lot about you from your social media activity. One of their experiments involved exploring emojis. About a fifth of posts on Twitter include emojis, so they wondered if anything could be predicted about people, ignoring what they wrote and just looking at the emojis they used in their tweets. They found that the way people use emojis in twitter posts alone gives away whether they are male or female and their ethnic background.

They started by taking a large number of tweets known to be written by either men or women and stripped out the words, leaving only the emojis they used. They then counted how often each group used different emojis. The differences in use of each emoji seemed to be revealing as there was clearly a different pattern of use overall of each emoji by men and by women. Men and women each use some emojis much more than others.

Next, they used emoji data for some of the people to train a machine learning system (creating what is known as a classifier). The classifier was given all the emojis used by a person and told which were by men and which by women. It built up a detailed pattern of what a man’s emoji profile was like and similarly what a woman’s was like. 

Given a new set of tweets from a single person the classifier could then try to predict man or woman based on whether that profile was closer to the male pattern or closer to the female pattern of emoji use. Walid’s team found their emoji classifier’s predictions were right about 80% of the time – essentially it was as accurate as doing a similar thing based on the words they wrote. When they tried a similar experiment with ethnicity (was the person black, white or of another ethnicity) the predictions were even more accurate getting it right 84% of the time.

A lot can be worked out about you from apparently innocuous information that is publicly available as a result of your social media use. Even emojis give away something of who you are 😦

Paul Curzon, Queen Mary University of London, Spring 2021

– Based on a talk given by Walid Magdy at QMUL, May 2021.

Back (page) to health

Improvements in technology and decision making are transforming the way we look after our health. Here are some more interesting ideas to keep people alive and well.

Woman wearing VR headset looking at the sky.
Image by Pexels from Pixabay

The future is in your poo

You’ve heard of telling a person’s future from reading their tea leaves. Scientists believe an effective way of seeing a town’s future may be in the poo. By looking for infection in the waste at sewerage works it’s possible to get fast and accurate local knowledge of where infection rates are high and where low to feed into decision making tools.

Health advice: Stay in the toilet, Stay safe. Help the NHS.

Virtually breaking quarantine

The game, World of Warcraft, a multi-user dungeon game, helped virologists understand how people might behave in pandemics. The game’s developers released a plague that could be passed between avatars. The game’s contaminated area was quarantined. Rather than dying out, the virus escaped – because people broke into the quarantined areas to gawk, then left taking the virus with them.

Health advice: Your avatar should obey quarantine rules too!

The missing bullet holes

To stay healthy in a war, avoid being hit by a bullet. In World War II, many aircraft returned badly damaged. Abraham Wald studied them to decide where better armour was needed. There were more bullet holes in the fuselage than the engines. Where would you add the armour? Abraham added it where there were no bullet holes. He reasoned that the lack of holes in places like engines on returning planes meant that being hit there brought the plane down. Being hit elsewhere did not kill the pilots as those planes made it home!

Health advice: Dodge bullets by making good decisions …

Cybersick of virtual reality

The AI can detect puke-inducing movement and automatically correct the image.

A problem with virtual reality is that wearing a headset can be so immersive that it makes some people actually sick. This happens if you move about when watching a 3D video that was shot from a single place. Artificial intelligence software has come to the rescue, detecting puke-inducing movement and automatically correcting the image.

Health advice: If no bucket, always keep an AI handy.

Shining light on cancers

Cancer treatments like chemotherapy and radiotherapy make patients ill. Some drugs make cancer sensitive to light, allowing tumours to be killed by painlessly shining light on them instead. Sadly, that’s not easy when cancers are inside the body. A new Japanese solution is an LED chip, based on the technology used by contactless payment cards to provide power from a distance. Surgeons place it under the skin and leave it there. They glue it in place using a sticky protein from the feet of mussels. It shines low-intensity green light on the cancer, shrinking it.

Health advice: Stick a chip to your tumour

Smart sometimes means no gadgets

Being smart about health doesn’t have to be high-tech or even involve drugs. Exercise, for example, can be as effective helping with depression as taking medicine. Being out in nature can help too, so sometimes it’s worth leaving the gadgets behind and just going for a walk to enjoy the beauty of nature.

Health advice: Walk weekly in the woods

Paul Curzon, Queen Mary University of London, Spring 2021

Download Issue 27 of the cs4fn magazine on Smart Health here.

This post and issue 27 of the cs4fn magazine have been funded by EPSRC as part of the PAMBAYESIAN project.

Gadgets based on works of fiction

Why might a computer scientist need to write fiction? To make sure she creates an app that people actually need.

Portrait images of lots of people used as personas.

Writing fiction doesn’t sound like the sort of skill a computer scientist might need. However, it’s part of my job at the moment. Working with expert rheumatologists Amy MacBrayne and Fran Humby, I am helping a design team understand what life with rheumatoid arthritis is like, so they can design software that is actually needed and so will be used and useful.

A big problem with developing software is that programmers tend to design things for themselves. However, programmers are not like the users of their software. They have different backgrounds and needs and they have been trained to think differently. Worse, they know the system they are developing inside out, unlike its users. An important first step in a project is to do background research to understand your users. If designing an app for people with rheumatoid arthritis, you need to know a lot about the lives of such people. To design a successful product, you particularly need to understand their unfulfilled goals. What do they want to be able to do that is currently hard or impossible?

What do you do with the research? Alan Cooper’s idea of ‘Personas’ are a powerful next step – and this is where writing fiction comes in. Based on research, you write descriptions of lots of fictional characters (personas), each representing groups of people with similar goals. They have names, photos and realistic lives. You also write scenarios about their lives that help understand their goals. Next, you merge and narrow these personas down, dropping some, creating new ones, altering others. Your aim is to eventually end up with just one, called a primary persona. The idea is that if you design for the primary persona, you will create something that meets the goals of the groups represented by the other personas it replaced.

The primary persona (let’s call her Samira) is then used throughout the design process as the person being designed for. If wondering whether some new feature or way of doing things is a good idea, the designers would ask themselves, “Would Samira actually want this? Would she be able to use it?” If they can think of her as a real person, it is much easier to make decisions than if thinking of some non-existent abstract “user” who becomes whatever each team member wants them to be. It helps stop ‘feature bloat’ where designers add in every great idea for a new feature they have but end up with a product so complex no one can, or wants to, use it.

As part of the Queen Mary PAMBAYESIAN project we have been talking to rheumatoid arthritis patients and their doctors to understand their needs and goals. I’ve then created a cast of detailed personas to represent the results. These can act as an initial set of personas to help future designers designing apps to support those with the disease.

If you thought creative writing wasn’t important to a computer scientist, think again. A good persona needs to be as powerfully written and as believable as a character in a good novel. So, you should practice writing fiction as well as writing programs.

Read some of our personas about living with rheumatoid arthritis here.

– Paul Curzon, Queen Mary University of London, Spring 2021

See the related Teaching London Computing Activity

Find out more about goal-directed design and personas from its creator in Alan Cooper’s wonderful book “The inmates are running the Asylum” (the inmates are computer scientists!)

Download Issue 27 of the cs4fn magazine on Smart Health here.

This post and issue 27 of the cs4fn magazine have been funded by EPSRC as part of the PAMBAYESIAN project.

How do you solve a problem like arthritis?

Some diseases can’t be cured. Doctors and nurses just try to control the disease to stop them ruining people’s lives. Perhaps smartphone apps can pull off the trick of giving patients better care while giving clinicians more time to spend with the patients who most need them? A Venn diagram is at the centre of the Queen Mary team’s prototype.

A Venn diagram of low participation, low empowerment and low independence with images linked to each - people eating in a resterount, a person holding out arms at the top of a peak and two people walking.

What is rheumatoid arthritis?

Normally your immune system does a good job of fighting infection and keeping you healthy. But, if you have an autoimmune disease, it can also attack your healthy cells, causing inflammation and damage. Rheumatoid arthritis is like this: a painful condition that mostly affects hands, knees and feet as the person’s immune system attacks their joints, making them swell painfully. It affects around 400,000 people in the UK and is more common in women than men.

People with the disease alternate between periods when it is under control and they have few symptoms, and with days or weeks of painful ‘flares’ where it is very, very bad. During these flares it especially affects a person’s ability to live a normal life. It can be hard to move around comfortably, do exercise – plus it interferes with their ability to work. It can also leave them totally reliant on family and friends just to do everyday things like dress or eat, never mind go out. This can lead to depression and puts a strain on friendships.

Treating the disease

Treatment, which can include tablets, injections, physiotherapy and sometimes surgery, slows the disease, keeping it under control for long periods. Sufferers are also given advice on lifestyle changes. This all reduces the risk of joint damage and helps people live their life more fully.

At appointments, doctors collect information to help them see how the disease is progressing. A Disease Activity Score (DAS) calculator lets them combine measurements for pain, how tender or swollen their patient’s joints are and how many joints are affected. Regular blood tests keep track of the amount of inflammation and how the body is reacting to drugs. This helps them decide if they need to adjust the medication.

If it is caught early, modern medicine reduces the worst effects of the disease, helped by keeping a close eye on the Disease Activity Score as treatments may need to be repeatedly adjusted to control flares. This requires regular hospital visits which uses up scarce healthcare resources and is very time-consuming for patients. It is hampered because hospital appointments may only happen twice a year due to the number of patients. Everyone wants to give more personalised care, but hospitals just can’t afford to provide it.

Supporting doctors

So, what do you do when there just aren’t enough doctors to see everyone as regularly as needed to maintain their patients’ wellbeing? One solution is to use remote monitoring with an app on a patient’s smartphone, so involving patients more directly in their own care. They can use such apps to regularly record their own disease activity measurements, sharing the information with their doctor to save visiting the hospital.

A smart app

This is an improvement, but the measurements still require expert monitoring and can take more of the doctor’s time. However, if smartphones can actually be made to be, well, smart, then they could help give advice between hospital visits and alert the hospital team, when needed, so they can step in. This might involve, for example, loading the app with background knowledge about rheumatoid arthritis, expert knowledge from lots of doctors, and creating an artificial intelligence to use this information effectively for each patient.

Hospital specialists and computer scientists at Queen Mary are developing such a prototype based on Bayesian networks as the artificial intelligence core. Bayesian networks are based on reasoning about the causes of things and how likely different things are to be the cause of something being observed. Building the prototype involves finding out if patients and clinicians find such tools useful and acceptable (some people might find clinic visits reassuring, while some may be keener to avoid taking the time off work, for example).

Smart and patient centred

This still focusses on a clinician’s view of treatment using drugs though. With a smartphone app we can perhaps do better and take the person’s life into account – but how? The first step is to understand patient goals. Patients would need to be willing to share lots of information about themselves so that the software can learn as much as possible about them. Eventually, this might be done using sensors that automatically detect information: how much pain they are in, how stiff their joints are, how much they move around, how long it takes them to get out of a chair, how much sleep they get, how often they meet others, if and when they take their medicine, and so on. Rather than just focussing on medical treatment it can then focus advice ‘holistically’ on the whole person.

The Queen Mary team’s approach is centred around three different things: helping people with physical independence so they can move around and look after themselves; empowering them to manage their condition and general well-being themselves; and participation in the sense of helping them socialise, keep friendships and maintain family bonds.

The Bayesian network processes the information about patients and computes their predicted levels of independence, empowerment and participation, working out how good or bad things are for them at the moment. This places them in one of seven positions in a Venn diagram of the three dimensions over which areas need most attention. It then gives appropriate advice, aiming to keep all three dimensions in balance, monitoring what happens, but also alerting the hospital when necessary.

So, for example, if the Bayesian network judges independence low, participation high and empowerment low, the patient is in the Venn diagram intersection of low empowerment and low independence. Advice in the following weeks, based on this area of the Venn diagram, would focus on things like coping with pain and stiffness, getting better sleep, as well as how to manage the disease in general.

By personalising advice and focusing on the whole person, it is hoped patients will get more appropriate care as soon as they need it, but doctors’ time will also be freed up to focus on the patients who most need their help.

– Jo Brodie, Hamit Soyel and Paul Curzon, Queen Mary University of London, Spring 2021

Download Issue 27 of the cs4fn magazine on Smart Health here.

This post and issue 27 of the cs4fn magazine have been funded by EPSRC as part of the PAMBAYESIAN project.

Are you there yet?

Plenty of people love the Weasley family’s clock from the Harry Potter books and films. It shows where members of the family are at any given time. Instead of numbers giving the time, the clock face has locations where someone might be (home, school, shopping) and the many hands on the clock show the family members. The wizarding world uses magic to make their whereabouts clock work, but muggles (and squibs) can use mobile network data to build a simple version, and use Bayesian networks to improve it.

A cell phone tower looking up from inside to a blue sky

Your mobile phone is in contact with several cell towers in the mobile provider’s network. When you want to send a message, it goes first to the nearest cell tower before passing through the network, finally reaching your friend’s phone. As you move around, from home to school, for example, you will pass several towers. The closer you are to a tower the stronger the signal there, and the phone network uses this to estimate where you are, based on signal strength from several towers. This means that, as long as your phone is with you, it can act as a sensor for your location and track you, just like the Weasley’s whereabouts clock.

You could also have a similar system at home that monitors your location, so that it switches on the lights and heating as you get closer to home to welcome you back. On a typical day you might head home somewhere between 3 and 6pm (depending on after-school events) and as you leave school the connection to your phone from the tower nearest the school will weaken, but connections will strengthen with the other cell towers on your route home. But what if you appear to be heading home at 11 in the morning? Perhaps you are, or maybe actually the signal has just dropped from the tower nearest to the school so a tower nearer your home is now getting the strongest signal!

A system using Bayesian logic to determine ‘near home’ or ‘not near home’ can be trained to put things into context. Unless you are ill, it’s unlikely that you’d be heading home before the afternoon so you can use these predicted timings to give a likelihood score of an event (such as you heading home). A Bayesian network takes a piece of information (‘person might be nearby’) and considers this in the context of previous knowledge (‘and that’s expected at this time of day so probably true’ or ‘but is unlikely to be nearby now so more information is needed’). Unlike machine learning which just looks for any patterns in data, in a Bayesian networks approach the way one thing being considered does or does not cause other things is built in from the outset. Here it builds in the different possible causes of the signal dropping at a cell tower.

You could also set up a similar system in a home using wifi points to predict where you are and so what you are doing. Information like that could then feed data into a personalised artificial intelligence looking after you. Not all magic has to be run by magic!

-Jo Brodie, Queen Mary University of London, Spring 2021

Download Issue 27 of the cs4fn magazine on Smart Health here.

This post and issue 27 of the cs4fn magazine have been funded by EPSRC as part of the PAMBAYESIAN project. This article was inspired by

Inspired by the blog on Presence Detection Part 1: Home Assistant & Bayesian Probability and a previous cs4fn article on making a Whereabouts Clock.

So, so tired…

Fatigue is a problem that people with a variety of long-term diseases can also suffer from.

A man, hands over face, very, very tired.
Image by Małgorzata Tomczak from Pixabay

This isn’t just normal tiredness, but something much, much worse: so bad that it is a struggle to do anything at all, destroying any chance of a normal life. Doctors can often do little to help beyond managing the underlying disease, then hope the fatigue sorts itself out. Sometimes fatigue can stay with the person long, long after. Maha Albarrak, for her PhD, is exploring how computer technology might help people cope. Her first step is to interview those suffering to find out what kind of help they really need. Then she will work closely with volunteers to come up with solutions that solve the problems that matter.

– Paul Curzon, Queen Mary University of London, Spring 2021

Download Issue 27 of the cs4fn magazine on Smart Health here.

This post and issue 27 of the cs4fn magazine have been funded by EPSRC as part of the PAMBAYESIAN project.