According to a 2008 "36-Hospital Time and Motion Study" conducted by The Permanente Journal, a considerable portion of a registered nurse’s day is spent on "wasted time", including delivering and retrieving items. In my discussions with the Veterans Affairs (VA) staff members, they were interested in having robotic transporters working in the hospital to help them with general delivery and retrieval tasks. I learned that existing robotic transporters do not use Artificial Intelligence (AI) to create routes from one point in the hospital to another, but are primarily preprogrammed to follow standard routes. Unlike a hospital transporter that uses limiting pre-programmed navigational routes, fully AI driven transporters would be capable of accessing more parts of the hospital to fully aid the nurses. 

Current pathfinding software uses heuristics (“rules of thumb”) from game theory AI, in which pathfinding is used to control the movement of virtual characters in a computer game. Accuracy is not considered in game theory AI, as these virtual characters are not impacted by outside forces. However, robots used in hospitals could slip on spilled water, run low on battery power, or otherwise become off-target. In these instances, the transporter would need to calibrate its position using landmarks, such as walls or colored floor tiles.

Many pathfinding heuristics link “path nodes” (points where a robot could move) to create paths. These path nodes are similar to the hallway intersections found in hospitals, as a path could be created by linking different nodes together.

“Breadth first search” works by finding a path that uses the fewest path nodes to reach its destination. However, the search does not compare the length of the path, and therefore, may actually find a path that uses very far-apart nodes. Another algorithm, called “best first search”, is similar to breadth first search, but starts creating the route from the ending point, rather than from the starting point. This is efficient unless there are obstacles in the way of its path. If there are, the algorithm will cause the route to “zig-zag” around the obstacle, making a route that is not efficient. 

A search called “A*” (pronounced A-star) uses a distance heuristic to search routes that are closest to the ending point. It combines the efficiency found in the best first search while also finding the shortest path possible. The algorithm works by using a field of path nodes, some of which may be occupied by an obstacle. At the starting point, the algorithm considers the surrounding nodes and creates a score for each possible movement. This score is based on the ease of the movement and whether the movement leads the path toward the destination. Then, it uses the node with the lowest point value as its new starting point. When this is run recursively until the path reaches the ending point, the resulting path is very efficient. While ideal for computer games, I wondered if an improvement to A* could be developed for robotic transporters. 


Figure out what others have found out about your subject area or question. How has your research helped you to refine your question and ask something that may not be unique, but is relevant and interesting and not already answered.


Judges' Tip
Excellent students will undertake research to help them shape their question and hypothesis and to put their work into a relevant, real-world context (500 words maximum).