-We present the design of a novel cognitive rehabilitation problems [2]. Recently, the use of computerized tools for tehxeerMcisSe-Rfeohratbhesyrestheambi.liItnattihoins eoxfeerxceisceu,ttivhee fpuantcietinotnhsatsotiontpelgarnataetiwntoo- cognitive training in MS has been increasing, as opposed to the day vacation in Rome by reserving the trains and hotel, and planning traditional pen-and-paper approach (see for example [3], [4]). the itinerary in the city while taking into consideration a number of The aim of this paper is to present the design of a constraints, mirroring the kind of limitations one would have to plan novel cognitive rehabilitation exercise for the rehabilitation of faourt oinmraetaeldlifepl(asnunchinags otopencoinngsthaonutrlys agnednbeurastsechneedwulesp)r.oWbleemexsplobiyt executive functions to integrate into MS-Rehab, an advanced combining randomly the different tasks to be carried out and to give system able to integrate the various phases of the MS hints to the users during rehabilitation. The exercise was carefully cognitive rehabilitation process [5]. designed to be as realistic as possible, thus having a high ecological Executive function is an umbrella term used to denote the lviafeli.dity and to maximize the positive impact on the patients quality of set of higher-order processes widely accepted as fundamental Index Terms-multiple sclerosis, cognitive rehabilitation, executive components of human cognition; indeed, studies have shown functions, planning, brain games that executive function deficits may lead to social and behavioral problems. Planning is one of the main skills related to executive functions, and a requirement of many cognitive I. INTRODUCTION and motor tasks. Specifically, it may be defined as the ability to organize cognitive behaviour in time and space and is necessary in situations where a goal must be achieved through a series of intermediate steps each of which does not necessarily lead directly towards that goal. The ability to plan is precisely the skill that the exercise we have developed, named Weekend in Rome, aims to train. The scenario which is simulated is different from any other present in rehabilitation software and had to be designed from scratch, involving a number of meetings with psychologists and rehabilitation experts to ensure its clinical validity. In this exercise, the patient has to plan a two-day vacation in the italian capital. In addition to making train and hotel reservations, he is also given a list of tasks (such as locations to visit or events to attend) he must accomplish, navigating all the difficulties which are typical of planning a trip in real life (reservations, bus schedules, opening hours...). Indeed, the exercise was carefully designed to be as realistic as possible, thus having a high ecological validity and to maximize the positive impact on the patients quality of life. The exercise was built using automated planning, a branch of artificial intelligence related to decision theory, which involves devising a plan, described as a sequence of actions, in order to achieve a given goal. Like all the other exercises of the MS-Rehab system, Weekend in Rome incorporates different auto-adaptive levels of difficulty.
Multiple sclerosis (MS) is one of the most common disease
of the central nervous system, affecting about 2 1/2 million
people worldwide. Specifically, it is an inflammatory
demyelinating disease: this means it is caused by damage to
the myelin, a lipid-rich substance that surrounds the axon of
some nerve cells, and allows a nerve to transmit its impulses
rapidly. Thus, the loss of myelin in MS is accompanied by a
disruption in the ability of the nerves to conduct electrical
impulses to and from the brain. This produces the various
symptoms of MS, which vary widely and include deficits in
movement, sensation, visual and bodily functions. In
particular, researchers indicate that 43 to 70% of patients are
cognitively impaired [
The term executive function covers a wide range of concepts: most researchers, in fact, agree that it is an exceptionally broad term, and there is little consensus on a precise definition. Nevertheless, it is indisputable that the term refers to abilities which are critical for functioning in everyday life: for example, executive functions help you manage life tasks such as planning a trip, your day, a research project or even something as basic as preparing a meal. Metaphorically speaking, executive functions could be considered the brains chief executive officer, the conductor of all cognitive skills. In fact, some abilities encompassed in executive functioning involve other cognitive domains as well, such as memory and attention. These abilities include the maintenance and manipulation of information, temporal organization, set shifting, self-monitoring, concept formation, verbal fluency, inhibition, motivation, organization, and planning. Widely accepted as fundamental components of human cognition, studies have shown that executive function deficits may lead to social and behavioral problems, as well as academic underachievement [6]: people who have difficulty inhibiting themselves, remembering things, planning, problem solving, and being flexible will present major deficiencies in social, academic, and vocational functioning. Executive functions gradually develop and change across the lifespan of an individual and can be improved at any time over the course of a persons life [7]. Here we concentrate on planning capabilities. Specifically, planning may be defined as the ability to organize cognitive behaviour in time and space and is necessary in situations where a goal must be achieved through a series of intermediate steps, each of which does not necessarily lead directly towards the specified goal [8]. Simply put, planning is the ability to think about the future and mentally anticipate the right way to carry-out a task: this means to choose the necessary actions to reach a specific goal, decide the right order, assign each task to the proper cognitive resources, and establish a plan of action. In order to plan efficiently, one needs the necessary information and the ability to mentally establish an adequate synthesis of all the data.
The ability to plan depends on elements like brain plasticity
or neuroplasticity, myelinization, or the ability to establish new
paths and synaptic connections. An absence or deficiency in
this ability is a typical symptom of frontal lobe disorders,
especially disorders that affect the prefrontal dorsolateral
area. Any task that requires planning, organization,
memorization, time management, and flexible thinking will be
particularly challenging for subjects who have deficient
planning abilities. Having significant difficulties in carrying out
these kind of tasks is known as dysexecutive syndrome (DES)
[
Cognitive rehabilitation therapy (CRT) is a broad term used
to describe treatments that address these cognitive problems.
The Institute of Medicines 2011 [
We give a few example of cognitive exercises designed to
test, restore or strengthen underlying cognitive functions, in
particular planning, with a high ecological validity. Exercises
with a high ecological validity are exercises which train the
patient on typical tasks required in day-to-day life, thus giving
rehabilitation a positive impact on the patients quality of life.
• Zoo Map: In 1996, Wilson, Alderman, Burgess, Emslie,
and Evans developed the Behavioral Assessment of the
Dysexecutive Syndrome (BADS), an ecologically valid test
battery designed specifically for the assessment of
planning and organizational capacity for situations one
could encounter in everyday life. Up until then,
conventional executive function tests lacked ecological
validity, resulting in a discrepancy between test
performance and functioning in everyday life [
Planning is one of the executive functions of the brain, and thus a fundamental property of intelligent behavior. It involves the explicit deliberation process that chooses and organizes actions by anticipating their outcomes, aiming at achieving some pre-stated objectives. Automated planning is the computational study of this deliberation process. In particular, plans are needed in many different areas of human endeavor and often it is useful, if not essential, to create these plans auto- matically. Automated planning technology now plays a significant role in a variety of applications, ranging from controlling space vehicles (such as the Mars Rover), managing fire extinctions or controlling underwater vehicles. Specifically, given a description of the possible initial states of the world, a description of the desired goals, and a description of a set of possible actions, the planning problem is to synthesize a plan that, when applied to an initial state, is guaranteed to bring us to a goal state which contains all the desired goals. As depicted in Figure 1 the main elements of a planning problem are characterized by the following components: • State-transition system: a formal representation of the real-world system we want to build plans for; visit the monuments, taking into account the duration of the visits and the appointments. Here, the setting was changed from Florence to Rome, and the time frame was increased from a single day to a weekend (two days). This allowed us to make the exercise even more realistic, thus increasing its ecological value, by adding the train and hotel reservations to the tasks the patient must accomplish in order to plan the vacation: the patient has to choose the train trip which allows him to arrive at the right time and the hotel located in the right place in order to complete all the tasks.
At first, a few locations in Rome were selected among the most famous tourist attractions, chosen between two categories: locations which could be visited, and locations where • Controller performs actions that change the state of the system; • Planner: produces the plans which drive the controller.
In 1998, in an attempt to standardize Artificial Intelligence
planning languages, Drew McDermott and his colleagues
proposed the Planning Domain Definition Language (PDDL)
[
The first step of the design phase of the exercise was laying the groundwork and devising the basic concepts of the exercise. This was followed by a precise analysis of the domain and actions in the exercise, and the formalization in PDDL.
The initial objective was to formulate how the basic structure of the exercise. Weekend in Rome was inspired by one paper-based exercise for executive functions rehabilitation used at the Bellaria Hospital in Bologna, Map of Florence: in this exercise, the patient is given a stylized map of Florence and a list of monuments or places to visit (for example, the Uffizi Gallery or the Piazza del Duomo), as well as some fixed-time appointments (for example, meet your friends for lunch at 1pm), and a starting time and location. The patient then has to plan the visit, choosing in which order to an event could occur (such as a concert). The chosen locations were: the Trevi fountain, Saint Peters Basilica, the Colosseum, the Pantheon, the Auditorium, the Ara Pacis, the Olympic Stadium and the Trastevere neighbourhood. The intent was to have some variety in the type of goals, which could range from the classic visiting a tourist attraction (such as the Trevi fountain), to attending a planned public event (such as a concert at the Auditorium or a football match at the Olympic Stadium) or a social occasion (such as having lunch with your friends in Trastevere). To increase the realistic aspect all the more, the patient is given two options for moving around the city: by foot, or by bus. In the latter case, bus timetables have to be taken into consideration as well. At this point, a semirealistic map (see Figure 2) with the chosen locations, the two train stations (Termini and Tiburtina), four hotels and possible bus routes was sketched in order to aid the modeling.
The next step was to choose the possible goals or tasks a patient had to accomplish. The immediate goals which could be defined were the train and hotel reservations. The latter imply that the patient has to sleep at the reserved hotel. To give a minimum of structure, it was decided to give a precise time at which the patient must go to sleep. Two additional tasks related to the hotel choice were defined to make the exercise more authentic: having breakfast at the hotel (taking into account breakfast hours), and exercising (doing gymnastics) before breakfast. In regards to the tasks pertaining to tourist activities, three main types were outlined: Simple sightseeing tasks; Activity tasks; Timed activity tasks.
From the very beginning the integration of automated planning for the exercises implementation was recognized as an essential requirement. One could argue that different approaches would have been possible: for example, given that the exercise basically consists in reaching a series of goals while satisfying certain constraints, one method which could come to mind is to solve the problem by modeling it as a constraint satisfaction problem (CSP). What makes automated planning a better solution is that while a CSP solver does find a solution in which all constraints are satisfied, a planner outputs the sequence of actions which can bring you to the solution, which is exactly what the pa- tient is required to do in order to train his executive functions. Thus, with automated planning, we can compare the planners solution to the patients to have a
performance metric. Moreover, the use of automated planning also allowed the implementation of a hint button (suggesting the next action to execute) and a verify button (giving the patient feedback on whether he is on the right track or not) as features of the exercise.
Once the specification of the exercise was well defined, the next phase was modeling it in PDDL. At first, the domain was formalized, extrapolating the different possible actions and predicates. The first step was to define the types of objects, that is the entities involved: in this case, two types were defined: time and place.
Time has to be modeled explicitly because the solver we
used (the PDDL4J library [
Modeling the domain also required a preliminary analysis to extrapolate the possible atomic actions in the different states. This resulted in the following list of actions: • Book train: the patient will use this action to choose which trains to book. There are two possible situations: the booking of a single journey, or the booking of a roundtrip. • Book hotel: action to choose the hotel to book, among the 4 available. • Wait: action to skip ahead in time of one hour. • Travel: action to move around on the map. Two kind of travel actions were implemented; travel by foot and travel by bus. Both of the actions have a duration of one hour; the advantage of traveling by bus was built into the map layout (i.e. some bus routes act as a shortcut between two places where two or more travel by foot actions would be needed to get from one to the other). • Sleep: action to go to sleep; two kind of sleep actions were implemented: a short sleep with the duration of four hours, and a long sleep with the duration of eight hours. These actions can only be executed at the booked hotel and at the determined sleep time, fixed by a specific predicate. • Have breakfast: action (with the duration of one hour) to be done at the hotel after sleeping, during the breakfast hours of the hotel. • Do activity: this action represents the different activities that can be done in the different locations (visit the exhibition, do the guided tour, watch the football match...).
For simplicity, it was determined that all the activities have the duration of two hours. • Exercise: this action has the duration of one hour, and must be done before breakfast.
During the definition of the actions, additional predicates to express accurately the preconditions and effects emerged as well. Train predicates are used to define the possible outward, return or round-trip journeys that are available for booking. Map predicates are used to model the underlying map of Rome and its mechanics, such as foot-path and bus-path to specify which locations are accessible with which kind of transport, opening-hours to define the opening hours of the different locations, can-sleep and train-station to denote whether a location is a hotel or a train station, breakfast-hours to define the hours during which breakfast is available at the hotel, and activity-available to mark the locations where an activity is available. Predicates to keep track of goals are used to keep track of the actions that have already been done, in order to identify when all the goals have been satisfied. Some examples are slept, visited, done-activity, done-activity-timed and doneexercise.
An example of action formalized using PDDL is presented in Figure 3. The action Travel by Bus specifies that you can travel by bus from a location ?src at the hour ?departuretime and to a location ?dst arriving at the hour ?arrival-time. The preconditions dictate that: the patient has to have finished the reservations; the patient has to be in the start location at the departure time; the arrival time must be hour immediately following the departure time; there must be a bus path between the two locations; the arrival time must be in the future; there must be a bus scheduled on that route at the departure time The effect equation says that, once the action is applied, you are at the destination at the arrival time, are no longer at the source location at the departure time, the departure time and the arrival time are in the past (i.e. no longer in the future), and the destination is marked as visited.
Subsequently, a common structure for all the problem instances was identified. Specifically, the common basis consisted in: • Objects: the objects involved are the same for each problem: the locations and the 48 hours • Initial state: most of the initial state description is common to all instances, namely the predicates to model the map and to model time.
Weekend in Rome adopts original solutions concerning the use of automatic planning in exercises for the rehabilitation of executive functions. We present these solutions comparing Weekend in Rome with other similar exercises based on planning, namely two currently available planning exercises in the MS-Rehab system (Plan-A-Day and ZooSafari visit), and the Plan a Holiday exercise of the RehaCom cognitive training software.
The MS-Rehab version of Plan-A-Day is based on the penand-paper version by Funke & Kruger. In this exercise, the patient has to schedule a list of tasks to complete during the day (for example, picking up his daughter from the swimming pool or buying groceries) while considering various constraints about when, where, and for what duration the activities have to be carried out. Conceptually, the exercise is similar to Weekend In Rome: the patient has to move around on a map and execute given tasks. However, in Weekend in Rome, there is the additional difficulty of having to plan the train and hotel reservations beforehand. In regards to the implementation, one main difference is that in Plan-A-Day, the planner is called after every action of the patient: if the new problem has a solution, the patient may continue, otherwise the exercise ends. This approach was not adopted for Weekend in Rome as there was a risk of having long loading times while the planner searched for a solution, making the exercise slow and bothersome. Another difference is that in the case of PlanADay, a new map is generated for each exercise; in Weekend in Rome, there are 3 static maps (corresponding to the 3 difficulty levels). The complete map presented in Figure 2 is associated to the high level, the easy and medium level maps are obtained from this map removing some of the locations and are illustrated in Figures 4 and 5. The logic for moving around on the map was also changed from drag & drop to clicking, as the first proved to be not easy to use for patients on tablet.
ZooSafari Visit was the second planning exercise implemented for MS-Rehab, inspired by the Zoo Map test. In this exercise, the patient has to plan his route through a map of the zoo, visiting a selection of locations while actively disregarding others and obeying certain rules: for example, the order of the locations to visit, or crossing certain paths only once. In this case the approach used in Plan-A-Day (calling the planner after each action of the patient) was also avoided. However, Weekend in Rome offers two additional features to exploit the planner, the Verify feature and the Hint feature: the Verify feature (see Figure 6) will give the patient an input on whether the problem is still solvable or not. In the latter case, it will inform the patient of which goal is unsolvable and give him the options to either continue in order to satisfy the other goals, or end the exercise. The Hint button instead will give
Fig. 5. Weekend in Rome Map: medium level. the patient a hint on which action to perform next. For both of these features, it is necessary to keep track of all the user actions in order to update the problem state.
A similar planning based exercise is available in the
RehaCom therapy system in the Plan a Vacation module, under
the name of Plan a HoliDay [
The rehabilitation of executive functions is essential for improving the quality of life of patients affected by multiple sclerosis, as their impairment compromises even the simplest day-to-day activities such as planning a meal or dressing oneself. If it is possible to improve executive functions through rehabilitation, then more people with MS might become more independent with activities of daily living, and might respond better to their rehabilitation. The objective of this work was the design and implementation of a novel exercise for the rehabilitation of executive functions and its subsequent integration in the the MS-Rehab system. In this exercise, the patient has to plan a two-day vacation in Rome by reserving the trains and hotel, and planning the itinerary in the city while taking into consideration a number of constraints, mirroring the kind of limitations one would have to plan for in real life (such as opening hours and bus schedules). This leads to the first key aspect of the exercise: its high ecological value. Indeed, while there are quite a few computerized cognitive rehabilitation exercises which involve planning a day into the city, none of them take place in a two-day span nor include the train and hotel reservations. A second important aspect is the generation of constantly new problems by combining randomly the different tasks to be carried out. Careful attention was also given to the user interface, in effort to make it not only easy to navigate and intuitive for the patient, but also pleasurable and fun in order to encourage the patient to carry out the exercise even at home. Last but not least, a novel feature which is not present in the other two planning exercises of the MS-Rehab system was implemented: the Hint feature, in which the patient is suggested the next action to execute in order to carry out all the given tasks. The varying difficulty levels were carefully defined in collaboration with a psychologist specialized in cognitive rehabilitation, which also deemed the exercise suitable for its planned purposes, that is the rehabilitation of executive functions.
A possible extension of the exercise would be to add a budget constraint, implemented through numeric fluents in PDDL (which are not currently supported by the PDDL4J planner). The exercise could also be enriched with ulterior activities to be carried out as tasks, such as a boat ride on the Tiber, or a stroll in the Villa Borghese park. Maps representing other cities, such as Florence or New York, could be designed for variety.
Another possible, but more challenging extension, would be
to implement a 3D version of the exercise, in which the patient
has to navigate through the streets of the city in firstperson
view, eventually exploiting Virtual Reality technologies.
Indeed, VR offers the potential to develop human testing and
training environments that allow for the precise control of
complex stimulus presentations in which human cognitive and
functional performance can be accurately assessed and
rehabilitated. Although further studies are needed, some 3D
applications are effective in treating cognitive deficits in
people with neurological diagnoses [