The objective of the proposed research is to develop planning algorithms for household robots, which have been a long-standing topic in the robotics community. Although many works have been enhancing capabilities of household robots, they still lag far behind human-level performance in every sense. To develop household robots, planning is an indispensable research domain for the following reasons: task decomposition, decision optimization, generalization and adaptability, and feedback utilization. In this proposal, we focus on the research of planning algorithms for household robots by solving difficult planning problems. Specifically, our proposed research consists of three goals: 1) formulate challenging household tasks as an MDP or Partially Observable MDP problem; 2) propose novel hierarchical planning algorithms with a highlight of leveraging Large Language Models and Branch-and-Bound techniques; 3) validate efficiency and accuracy of the proposed methods via a diverse set of experiments in well-adopted household simulators.