In practical robot motion planning, robots usually do not have a full model of their surrounding, and hence no complete and correct plan can be prepared in advance. In other words, in real-world scenarios a mobile robot operates in a partially known environment, meaning that there exists incomplete information about the true state of several ‘hidden’ variables, such as open/closed doors, which may represent potential blockages of the path of the robot. Consequently, a robot may have a probability distribution estimation of the states of the hidden variables and a preference over the possible values of such hidden variables. In this paper, to deal with the problem of choosing optimal policies for planning in off-line mode, a linear programming model is developed that incorporates the probability distribution of hidden variables. Furthermore, a heuristic method is proposed for planning in the presence of numerous hidden variables which relies on optimistic assumptive planning and produces near-optimal policies.