# Autonomous Navigation Framework for Intelligent Robots Based on a Semantic Environment Modeling
## 2 Related Work
### Planning
#### 2.4.1 Mission Planning  
On robots, the mission planner generally performs as a \"task planner,\" while on SDV, it focuses on map-level navigation or route planning [3; 63].  
Task planners usually follow one of two different approaches: classical planning or decision-theoretic planning. One of the first works to integrate classical planners into robotics was the Stanford Research Institute Problem Solver (STRIPS) [64], first implemented on a real robot by [PERSON] [65]. The planning community standardized STRIPS-based planning by introducing the PDDL, which was later expanded to support temporal planning as well as [10]. [PERSON] et al. introducedthe ROSPlan framework [11] integrating PDDL 2.1 with the Robot Operating System (ROS), which is vastly used by the robotics research community. By using a Knowledge Base, ROSPlan is able to build the initial domain state automatically, validated the generated plan, and decide when to re-plan. [PERSON] et al. [66] showed that PDDL-planners could also work on dynamic environments when other agents follow a deterministic behavior. Researchers have been attempting to integrate Hierarchical Task Network (HTN) with task planning using different techniques. [PERSON] et al. [67] proposed the first Flexible ANML Actor and Planner (FAPE) that combined most of the Action Notation Modeling Language (ANML) [68] with HTN task decomposition. It also integrated acting that followed Procedural Reasoning System (PRS) refinements, plan repair and re-planning. However, it used non-recursive decomposition hierarchy which decreased the expressiveness of HTN planning.  
Nonetheless, classical planners generally do not perform well in a dynamic and unpredictable environment due to its linear nature, making it unable to reason about multiple outcomes. Decision-theoretic planning, on the other hand, tries to maximize the probability of success (also known as a maximum expected utility, MEU) for every possible action outcomes from any state the robot reaches during the plan execution. It can solve Markov Decision Processes (MDP) and even POMDPs, but its high computational cost makes decision-theoretic approaches prohibitive. Most of the research done in this field was trying to overcome this issue. [PERSON] et al. [69] tried to solve an approximated optimal policy by identifying which propositions are relevant and using this information to reduce the state-space. On a similar fashion, [PERSON] et al. [70] used a known initial state to model the world nondeterminism and restrict the planner to focus only on states that might be encountered during the plan execution.  
Some newer approaches tried to combine ontology and semantic knowledge into planning. Hence, ontological knowledge eases semantic, temporal, and spatial representations of the environment [4]. [PERSON] et al. [71] used semantic maps to extend the planner reasoning capabilities, aiding high-level tasks understanding. KnowRob [72] is a knowledge processing framework that combines episodic memory, mental simulation, and a generalized ontology to help a robot to reason, plan, and learn. This work, however, focused only on manipulation tasks [73].