- In planning under partial observability with sensing actions (PPOS) problems, the solution progresses from one sensing action to another, until sufficient information is gathered and the goal can be reached. In between sensing actions, one can use classical planning to derive the path to the next sensing action. We suggest an online algorithm that repeatedly selects the next sensing action to execute, and plans to achieve it in a classical setting. Our algorithm avoids the difficulty in representing and updating a belief space. Our heuristic uses landmarks, and we explain how landmarks can be computed over a relaxation of the PPOS problem. We compare our Heuristic Contingent Planner (HCP) to state-of-the-art, translation- based online contingent planners, and show how it solves many problems much faster than previous approaches.