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

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.

Competing interests

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.