The main research of this thesis is to generate a footstep trajectory rapidly for a humanoid robot in the environment. Being different from a mobile robot, a humanoid robot has the ability to step on and down or step across motion to overcome obstacles. We use the algorithm that is developed in this thesis and the database to achieve the goal of trajectory generation. The algorithm that is proposed in this thesis is based on the basic RRT (Rapid Random Tree) algorithm. By adding the footstep transition models, the Multi-RRT algorithm is used to generate a footstep path of the humanoid robot. However, there are a lot of moving obstacles in the human living life. The dynamic Multi-RRT algorithm is the method to avoid moving obstacles by modifying the original path that is generated by the Multi-RRT algorithm. In addition, some information of the environment affects the stability of the robot. For example, the quality of commands transmission is influenced by the strength of the wireless signal. Even though, we cannot measure all the measurement in the map, we use the way to predict the values. Finally, we propose the DDAO Multi-RRT algorithm by considering the cost map that is modeled by a Gaussian Process. With the information of the map and the time-varying footstep trajectory, the humanoid robot can reach the goal by automatically changing the path. In this way, the humanoid robot can blend into our daily life.