In this paper, we propose a new approach tohumanoid navigation through cluttered environments that ex-ploits knowledge about different obstacle classes and selectsappropriate robot actions. To classify objects from RGB imagesand decide whether an obstacle can be overcome by the robotwith a corresponding action, e.g., by pushing or carrying itaside or stepping over or onto it, we train a convolutionalneural network (CNN). Based on the associated action costs, wecompute a cost grid of the environment on which a 2D path canbe efficiently planned. This path encodes the necessary actionsthat need to be carried out to reach the goal. We implementedour framework in ROS and tested it in various scenarios witha Nao robot. As the experiments demonstrate, using the CNNthe robot can robustly classify the observed obstacles intothe different classes and exploit this information to efficientlycompute solution paths. Our system finds paths also throughregions where traditional planning methods are not able tocalculate a solution or require substantially more time.