We propose a sensor-based motion planning/replanning method for a humanoid that must execute a task implicitly requiring locomotion. It is assumed that the environment is unknown and the robot is equipped with a depth sensor. The proposed approach hinges upon three modules that run concurrently: mapping, planning and execution. The mapping module is in charge of incrementally building a 3D environment map during the robot motion, based on the information provided by the depth sensor. The planning module computes future motions of the humanoid, taking into account the geometry of both the environment and the robot. To this end, it uses a 2-stages local motion planner consisting in a randomized CoM movement primitives-based algorithm that allows on-line replanning. Previously planned motions are performed through the execution module. The proposed approach is validated through simulations in V-REP for the humanoid robot NAO.