페트리 넷 이완을 활용한 비실행성 설명 및 순차적 작업 계획

Petri Net Relaxation for Infeasibility Explanation and Sequential Task Planning

계획은 종종 상황 변화 또는 상황에 대한 이해 변화로 인해 변경됩니다. 때로는 실현 가능한 계획이 존재하지 않을 수도 있으며, 이러한 비실행성을 식별하는 것은 요구 사항을 조정해야 할 시점을 결정하는 데 유용합니다. 일반적인 계획 방법은 실현 가능한 경우 효율적인 단일 계획 수립에 초점을 맞추는 반면, 도메인을 업데이트하거나 비실행성을 감지하는 데는 덜 집중합니다. 본 논문에서는 강력한 불변식 생성, 효율적인 목표 도달 불가능성 감지 및 유용한 비실행성 설명을 가능하게 하는 페트리 넷 도달성 이완 방법을 제안합니다. 또한 목표 및 제약 조건 업데이트를 지원하기 위해 점진적인 제약 조건 해결기를 활용합니다. 실험 결과, 제안하는 시스템은 기준 방법과 비교하여 유사한 수의 불변식을 생성하고 최대 2배 더 많은 비실행성을 감지하며, 단일 계획 수립에서는 경쟁력 있는 성능을 보이고, 테스트된 도메인에서 순차적 계획 업데이트 성능이 우수합니다.

Plans often change due to changes in the situation or our understanding of the situation. Sometimes, a feasible plan may not even exist, and identifying such infeasibilities is useful to determine when requirements need adjustment. Common planning approaches focus on efficient one-shot planning in feasible cases rather than updating domains or detecting infeasibility. We propose a Petri net reachability relaxation to enable robust invariant synthesis, efficient goal-unreachability detection, and helpful infeasibility explanations. We further leverage incremental constraint solvers to support goal and constraint updates. Empirically, compared to baselines, our system produces a comparable number of invariants, detects up to 2 times more infeasibilities, performs competitively in one-shot planning, and outperforms in sequential plan updates in the tested domains.