For mobile robots, navigation in dynamic, real-worldenvironments is a complex and challenging task.Such environments are characterized by their com-plex structure and the movement of humans and ob-jects in them. In such cases, a navigating robot caneasily get blocked by moving humans and obstaclesand may become immobilized and not able to con-tinue its movement towards its goal position untilthe moving objects free its way. To avoid ever get-ting in such a situation, many researchers have triedto predict the motion of humans and obstacles. Fu-ture motion prediction allows the robot to estimateif the way it follows is going to be blocked and thuschange direction before it ever faces this situation.

Future motion prediction is an intrinsic behavior ofhumans. Consider the example of a man trying tocross a street. The man tries to estimate how longit will take for a vehicle to reach the point that hestands and then decides if he should cross the street. Generally speaking, a robot has to make decisionsabout the actions it should perform at each time stepconsidering the information its sensors provide aboutthe environment state. Thus, the robot has to solvea sequential decision problem. The solution of a sequential decision problem in acompletely observable environment, where the robotalways knows its state, is called a Markov DecisionProcess (MDP). When there is uncertainty or notenough information to determine the state of therobot, the problem is called a Partially ObservableMarkov Decision Process (POMDP).