arXiv:2607.06724v2 Announce Type: replace Abstract: LLM-based robot planners are fluent but cannot guarantee that their plans are executable or safe. Classical PDDL planners can guarantee symbolic validity, but only once the problem is fully specified, and they make poor use of an LLM's ability to read context and repair plans. We present EvoPlan, a neuro-symbolic framework whose guarantees are symbolic validity and satisfaction of a constraint learned from data. The planner works with locally-hosted open-weight models, so it does not require a cloud service. EvoPlan has three parts. First, an offline procedure that mines a single global Signal Temporal Logic (STL) mobility constraint from demonstrations. Perturbed demonstrations supply the missing negatives without encoding any rule, and evolutionary search fits the constraint, which captures driving rules or social-navigation preferences within a modelled taxonomy of norms. We use the mined constraint to shield driving and navigation policies on Bench2Drive and HA-VLN-CE. Second, an evolutionary PDDL planner: an LLM proposes and repairs plans, programmatic validators decide which ones survive, and the validated portion of the plan grows over iterations. On open-world ALFWorld and NL-PDDL Blocksworld, it approaches classical planning when the goal vocabulary agrees with the action model, and it stays robust when the two disagree and classical planning fails. Third, a constrained execution loop: Nav2 uses the costmap to ground the plan into waypoints, which are checked against the mined constraint. Violations and execution failures update the PDDL problem for re-planning. We demonstrate the full pipeline in Gazebo and on a Clearpath Jackal robot. More details and videos are on the project page: https://nbhavyasai.github.io/evoplan/