The Traveling Salesman Problem (TSP): A Spatial Navigation Task for Rats    

Edited by
Jena Hales Jena Hales
Reviewed by
Anonymous reviewer
How to cite Favorites Q&A Share your feedback Cited by

In this protocol

Original research article

A brief version of this protocol appeared in:
Animal Cognition
Nov 2015

 

Abstract

The Traveling Salesman Problem (TSP) is a behavioral test used to measure the efficiency of spatial navigation. It is an optimization problem, in which a number of baited targets are placed in an arena, and as the subject travels between the targets, the route is recorded and compared to chance and optimal routes. The TSP is appealing for the study of learning, memory, and executive function in nonhuman animals because the memory requirements can easily be modified with minor adjustments to task parameters. In the standard version of the task, rats are initially pre-trained to forage for bait in the arena. Once the animals consistently retrieve the bait, they are tested with a set of novel target configurations, and their behavior is recorded. The videos are then scored to produce several measures of performance.

Keywords: Spatial navigation, Cognition, Planning, Working memory, Executive function, Optimization

Background

The Traveling Salesman Problem (TSP) is a spatial navigation task in which participants are asked to select the shortest possible route that visits each target in a spatial array. This task has been of interest to computer and cognitive scientists for some time (Best, 2006), but has more recently been studied from the perspective of comparative psychology (e.g., de Jong et al., 2011; Gibson et al., 2012; Baron et al., 2015). Humans are inexplicably good at finding solutions to this problem – despite its mathematical intractability, human participants can rapidly and easily produce solutions that are nearly optimal (MacGregor et al., 2000). One possible explanation for this high level of performance is that the task capitalizes on evolved processes used for natural behaviors like foraging (Blaser and Ginchansky, 2012; Blaser and Wilber, 2013). We were therefore interested in the mechanisms by which non-human animals complete the task (Bellizzi et al., 2015; Goldsteinholm and Blaser, 2015).

Although human participants typically use either a computer or paper and pencil to solve the TSP, we used the radial arm maze as a model to design a comparable task for rats (Blaser and Ginchansky, 2012). The task has not been widely used with nonhuman animals, but already several variant procedures exist. For example, Bures et al. (1992) used a TSP design in which animals were not rewarded until after all targets had been visited, with subjects trained on the same target configurations for 10 consecutive days prior to testing. Miyata et al. (2010) required pigeons to peck at a touch-screen in order to receive a food reward at the end of the test. Important variations across procedures involve whether food is available at each target or only at the end, whether animals are exposed to a specific spatial configuration more than once, and the scale of the spatial arena relative to the body size of the animal. We selected a protocol in which novel configurations are tested to reduce the degree to which performance relies on long-term spatial memory, and in which a relatively large arena encourages distance minimization.

Materials and Reagents

  1. Rats
  2. Ethanol
  3. Targets
    1. Semi-transparent purple vinyl index card dividers (Oxford Esselte, catalog number: 73153 )
    2. Rodent food dishes
    3. Sterilized bottle caps
    Targets are pieces of plastic cut into 2” diameter circles. We use semi-transparent purple vinyl index card dividers by Oxford Esselte, but in the past have successfully used both rodent food dishes and sterilized bottle caps. The flat vinyl targets are appealing because they are simple to clean, and are less attractive to the rats to explore and carry, compared to dishes or caps. Whichever targets are employed, the targets used in a single experiment should be identical to each other.
  4. Bait
    1. Froot Loops® cereal (or a generic equivalent)
    2. Fruity Pebbles® or Cocoa pebbles® (one pebble per target)
    For bait, we use Froot Loops® cereal (or a generic equivalent) broken into quarter pieces (one quarter per target), or Fruity Pebbles® or Cocoa pebbles® (one pebble per target). All work equally well.
  5. Configuration Templates
    During pre-training, targets are placed randomly and do not require templates (see Procedure). In the test trials, however, the spatial arrangement of targets is critical. For this purpose, we create a template out of posterboard which is cut to fill the entire arena floor. Holes (approx. 2.5” diameter) are cut in the posterboard where the targets will be placed. Before each trial, the template is placed in the open field, and targets are then placed in the holes. The template can then be lifted out of the open field, leaving the targets located precisely in the arena.

Equipment

  1. Open Field Arena (Figure 1)
    The animals are tested in a 90 x 90 x 75 cm open field arena made of plywood. It is painted white, with a black grid painted on the floor. Any large standard open field should work, although the same type should be used consistently since the arena size and shape are expected to affect task performance measures.


    Figure 1. Photo of the open field arena with ten baited targets and a rat

  2. Stopwatch
    A simple stopwatch (minutes/seconds) is used to time the animals in the task.
  3. Video Camera
    A video camera recording high-definition video files to SD card is used to record all trials. The video camera resolution must be sufficient to see (1) whether a piece of bait has been removed from the target in low lighting conditions, and (2) whether the vibrissa (whiskers) of the animal contact the target.
  4. White Noise generator (e.g., HoMedics, model: SS-2000G/F-AMZ )
    We use a standard home-use white noise generator, HoMedics SS-200G/F-AMZ. Any standard model of white-noise generator designed for home or laboratory use would be appropriate. The white noise generator helps to mask any distractions due to extraneous sounds in or near the testing room, which reduces behavioral variability in the task.

Procedure

  1. Handling/gentling the animals
    See Figure 2 for a schematic diagram of the entire experimental timeline. Prior to testing, the individuals that will be handling the animals in the experiment should begin to handle (pick up and hold) each animal for a few minutes each day. If the bait is a novel food for the rats, a few pieces of the cereal can also be offered each day to acclimate the rats to the food. Animals should be handled a minimum of 4 days prior to the start of pre-training, but ideally 5-7 days.


    Figure 2. Experimental Timeline. The entire experiment takes approximately 18-24 days, including handling, pre-training, and testing. The entire timeline is represented schematically in this Figure.

  2. Food deprivation
    2-3 days before pre-training, food deprivation should begin. First, the baseline weights of all animals should be recorded, and then all food (but not water) should be removed for 24 h. After 24 h, limited food (about 40 g/rat) should be provided on a daily basis. Rats should be weighed each day, and the amount of food provided each day should be adjusted so that animals maintain approximately 85-90% of their baseline weight.
  3. Habituation
    The first day of the experiment, following about 2-3 days of food deprivation, is habituation. Habituation and all other training should occur during the rats’ dark cycle, at approximately the same time (i.e., within a 2-h time window) each day.
    1. Lights in the testing room should be dimmed to the lowest level at which the video-cameras can function–if red lights are available, the experiment can be run in darkness with red lights only. The white noise generator should be on.
    2. Animals are placed individually into the open field arena, and allowed to explore for 10 min. At the end of 10 min, the animals are removed from the arena, returned to their home cage, and fed.
    3. During habituation and all pre-training and test trials, the experimenter should either leave the room (monitoring the rat via video-camera), or sit still and quietly in a location set back from the open field. There should be no food, drinks, lotions, perfumes, jewelry, music, or other distracting stimuli present in the testing room.
    4. Between rats, the arena should be wiped down with an ethanol solution to clean and disperse odor cues.
  4. Pre-training
    After one day of habituation, pre-training begins. All environmental conditions such as lighting and white noise should remain the same as during habituation. Pre-training is run in stages, with animals needing to complete each stage before moving to the next. Animals receive one trial each day for the duration of pre-training. Therefore, the time to complete pre-training may vary, with animals usually requiring approximately 10-14 days.
    1. For the first stage of pre-training, four targets are placed randomly in the arena, with one piece of bait on each target. An individual rat is placed in a designated starting point, and allowed to forage for the bait. The trial ends when the rat retrieves all four pieces of bait, or when 10 min is up, whichever happens first. Stage one of pre-training is complete when the animal successfully retrieves all four pieces of bait on two consecutive trials.
    2. For stage two, six targets are placed in the arena, each with one piece of bait. Stage two is completed when the rat successfully retrieves all six pieces on one trial.
    3. For stage three, eight targets are placed in the arena, each with one piece of bait; completion requires the successful retrieval of all eight pieces on one trial.
    4. Finally, for stage four, 10 baited targets are placed in the arena. Stage four, and pre-training, are complete when the animal successfully retrieves nine out of the 10 targets on three consecutive trials. At this point, the animal can begin the testing phase of the experiment.
  5. Testing phase
    During the testing phase, animals are observed in the arena with a specific target configuration designed to answer a particular test question.
    1. The configuration template is first placed on the arena floor, then baited targets are placed, and finally the template should be removed before the rat is placed in the arena. As in pre-training, the behavior of the rat is recorded for 10 min, or until the rat retrieves all of the bait, whichever happens first.
    2. After the trial, the rat is placed back into the home cage and fed. The specifics of the configurations (number of targets, location of targets, number of different configurations) will depend on the experimental question. Configurations used in previous research studies (e.g., Blaser and Ginchansky, 2012) may be used for reference; see Figure 3 for examples of four 10-target configurations. Unless the order of testing different configurations is determined by the experimental question, the sequence should be balanced across rats when multiple configurations are used. See Video 1 for an example of a rat’s behavior in a test trial.


    Figure 3. Four example target configurations. A. Simple Baseline; B. Nearest-Neighbor Adequate; C. Cluster Approach; D. Nearest-Neighbor Inadequate. Four example configurations, all with 10 targets are provided in Figure 3. In 3A is a simple baseline configuration to determine baseline motivation and locomotor activity. In 3B is a configuration for which a simple nearest-neighbor strategy produces the optimal route. In 3C is a configuration to determine preference for target clusters. In 3D is a configuration for which the simple nearest-neighbor strategy produces a sub-optimal route.

  6. Video coding and analysis
    Once the trials are complete, the video files are coded for several behavioral measures. First, each target is given a unique number. The optimal route (shortest possible path) must also be determined for each configuration.
    Contact: Contact with a target is recorded when the whiskers, nose, or forepaw of the subject touch either the target or bait. Contact with a target by the tail or hind paws of the animal is not counted.
    Retrieval: Retrieval of bait is recorded when the subject removes the bait from the target (so all retrieval scores are automatically counted as contact with that target). These are recorded into a data file as a list of target numbers in the sequence in which they are contacted, with an additional flag (e.g., color code or highlight) to designate retrievals.

    Video 1. Video of a rat completing a test configuration

    Transitions: Transitions are calculated from the sequence of target contacts. A transition is defined as the line segment connecting two consecutive contacts. For example, if a subject contacts Target 2 then Target 4, a transition from 2 to 4 is recorded. This establishes a sequence of transitions for each animal on each trial. Optimal Transitions are the segments connecting target pairs along the optimal route. The distance between each target pair (cm) is used to calculate Total Travel Distance for each subject. Because transitions are used to calculate distance measures, these measures do not take into account deviations from the shortest path between two targets. If desired, the videos can also be played through a video-tracking program (such as Ethovision®, Anymaze®, or ViewPoint®) to establish actual travel distances as well.
    Memory Measures
    Revisits: Revisits are defined as any contact with a target after the bait from that target is retrieved.
    Omissions: Omissions are defined as any target that is not visited in the 10-min trial period.
    Span: Span is defined as the number of targets visited prior to the first revisit.
    Route Choice Measures
    Percent Above Optimal: Percent Above Optimal (PAO) is calculated as the difference between the total travel distance and the optimal route distance, divided by the optimal route distance. A lower score indicates better performance, since lower scores indicate shorter path lengths.
    Proportion of Optimal Transitions: The Proportion of Optimal Transitions is calculated as the number of transitions that fell along the optimal route, divided by the total number of transitions.
    Proportion of Distance on Optimal: The Proportion of Distance on Optimal is defined as the total distance traveled along the optimal route, divided by the total travel distance.

Data analysis

Most commonly, the behavioral measures can be compared between two experimental groups using a t-test (if only two groups), or an ANOVA (if multiple groups or repeated testing is needed). We typically use the standard definition of an outlier as a subject who scores at least 2 standard deviations above the mean–these are excluded from analysis.

Acknowledgments

The original inspiration for this line of research was from discussions with Dr. Ed Chronicle, to whom I am most grateful. The recent work has been supported by the University of San Diego Faculty Research Grants. The author has no conflicts of interest to declare.

References

  1. Baron, D. M., Ramirez, A. J., Bulitko, V., Madan, C. R., Greiner, A., Hurd, P. L. and Spetch, M. L. (2015). Practice makes proficient: pigeons (Columba livia) learn efficient routes on full-circuit navigational traveling salesperson problems. Anim Cogn 18(1): 53-64.
  2. Best, B. J. (2006). Cognitive Approaches to the Traveling Salesperson Problem: Perceptual Complexity that Produces Computational Simplicity. AAAI Spring Symposium: Between a Rock and a Hard Place: Cognitive Science Principles Meet AI-Hard Problems.
  3. Blaser, R. E. and Wilber, J. (2013). A comparison of human performance in figural and navigational versions of the traveling salesman problem. Psychol Res 77(6): 761-772.
  4. Blaser, R. E. and Ginchansky, R. R. (2012). Route selection by rats and humans in a navigational traveling salesman problem. Anim Cogn 15(2): 239-250.
  5. Bellizzi, C., Goldsteinholm, K. and Blaser, R. E. (2015). Some factors affecting performance of rats in the traveling salesman problem. Anim Cogn 18(6): 1207-1219.
  6. Bures, J., Buresová, O. and Nerad, L. (1992). Can rats solve a simple version of the traveling salesman problem? Behav Brain Res 52(2): 133-142.
  7. de Jong, L. W., Gereke, B., Martin, G. M. and Fellous, J. M. (2011). The traveling salesrat: insights into the dynamics of efficient spatial navigation in the rodent. J Neural Eng 8(6): 065010.
  8. Gibson, B., Wilkinson, M. and Kelly, D. (2012). Let the pigeon drive the bus: pigeons can plan future routes in a room. Anim Cogn 15(3): 379-391.
  9. MacGregor, J. N., Ormerod, T. C. and Chronicle, E. P. (2000). A model of human performance on the traveling salesperson problem. Mem Cognit 28(7): 1183-1190.
  10. Miyata, H. and Fujita, K. (2010). Route selection by pigeons (Columba livia) in "traveling salesperson" navigation tasks presented on an LCD screen. J Comp Psychol 124(4): 433-446.
Copyright: © 2018 The Authors; exclusive licensee Bio-protocol LLC.
How to cite: Blaser, R. E. (2018). The Traveling Salesman Problem (TSP): A Spatial Navigation Task for Rats. Bio-protocol 8(11): e2870. DOI: 10.21769/BioProtoc.2870.
Q&A

Please login to post your questions/comments. Your questions will be directed to the authors of the protocol. The authors will be requested to answer your questions at their earliest convenience. Once your questions are answered, you will be informed using the email address that you register with bio-protocol.
You are highly recommended to post your data including images for the troubleshooting.

You are highly recommended to post your data including images for the troubleshooting.

We use cookies on this site to enhance your user experience. By using our website, you are agreeing to allow the storage of cookies on your computer.