A new method for bipedal walking on rough terrain by using ZMP criteria map is proposed. The rough terrain walking is classified to “step up” and “step down” by landing timing of a swing leg. The walking pattern is modified in real-time according to the difference between the ideal timing and the measured timing by a force sensor on the foot. In the case of “step up”, the landing timing is faster than the ideal, and the swing leg trajectory should be change to follow the step so that the ZMP based balance of the sudden caused double support phase is kept. In the case of “step down”, the landing timing is later than the ideal, and the swing leg trajectory should be change to seek the ground so that the balance of the unknown future double support phase is kept. The modified walking pattern is decided based on the ZMP criteria map. The ZMP criteria map can indicate a safe landing timing and landing position of a swing leg. By referring the ZMP criteria map, the robust walking pattern can be planned. The proposed method is implemented to HRP-2, and the effectiveness is confirmed through experiments.