Explainable Planning for Hybrid Systems

Mir Md Sajid Sarwar

Figure 1

Figure 2

Figure 3

Figure 1.1 : XAIP perspectives

Figure 1.2 : The proposed organization to discuss the challenges and research directions in XAIP for hybrid systems.

Figure 2.1 : Stealth surveillance system for monitoring hostage scenario

Figure 2.2 : CoppeliaSim model of the quadruped robot

Figure 2.3 : The robotic software architecture for SLAM, path-planning, and control.

Figure 2.4 : Phases of Move-forward and Rotate-Clockwise maneuvering of the robot

Rot ( $\\|\theta_{1}\\|$ , $\\|\theta_{2}\\|$ )	Rot-diff ( $\gamma$ )	Eff-rot ( $\alpha$ )	Ratio ( $K$ )
$45\degree$ , $20\degree$	$25\degree$	$5.947\degree\approx 6\degree$	$4.204$
$40\degree$ , $20\degree$	$20\degree$	$4.535\degree\approx 4.5\degree$	$4.414$
$35\degree$ , $20\degree$	$15\degree$	$3.072\degree\approx 3\degree$	$4.883$
$30\degree$ , $20\degree$	$10\degree$	$1.485\degree\approx 1.5\degree$	$6.734$
$30\degree$ , $30\degree$	$0\degree$	$0\degree$	$-$

Table 2.1 : Clockwise and anti-clockwise rotations.

\theta_{1}

and

\theta_{2}

are angles of rotation of the joints in the first and second phases, respectively.

Figure 2.5 : Robot movement

Figure 2.6 : Robot’s trajectory

Figure 2.7 : Robot’s deviation from the path

Figure 2.8 : Hybrid controller

Environment				obs	var	cnstr	turns	replans	$T_{plan}$	$dist$	$T_{traverse}$	cov (%)	Remarks
Scene	Dim	Ins	Complexity	obs	var	cnstr	turns	replans	(in Sec)	(in Meter)	(in Sec)	cov (%)	Remarks
Scene-1	$10\times 10m^{2}$	$ins1$	Complex	$225$	$2779$	$1807$	$7$	$3$	$123.81$	$13.29$	$919$	$36.59$	Success
		$ins2$	Complex	$117$	$3056$	$1661$	$7$	$6$	Time Out	$2.61$	$526$	$21.16$	Failure
		$ins3$	Simple	$60$	$4$	$8$	$1$	$1$	$0.12$	$5.32$	$211$	$20.21$	Success
		$ins4$	Complex	$136$	$2405$	$1565$	$5$	$2$	$61.98$	$7.36$	$539$	$37.63$	Success
Scene-2	$5\times 5m^{2}$	$ins1$	Complex	$116$	$2246$	$1611$	$5$	$3$	$17.1$	$6.92$	$510$	$61$	Success

Table 2.2 : Simulation Results

Figure 2.9 : Planning and Navigation: simulation results of plan generation and navigation in an office-like environment using CoppeliaSim and ROS: (a) is shown here. The initial plan is given in (b) when most of the environment was unknown, assuming the unknown as free spaces. (c) shows detection of obstacles on the path, (d) and (e) present two re-planning steps at different time points during navigation, and (f) depicts the robot’s actual traversed path while following the generated plans.

Figure 3.1 : The hybrid automaton model of the Car domain

Figure 3.2 : Example scenarios where makespan is useful. In the figure,

t

encodes time, and

a

and

b

are variables.

Figure 3.3 : The Contrastive Plan Explanation Framework.

Figure 3.4 : The hybrid automaton for the corresponding HModel of the question is addressed in sect 4.1.

Figure 3.5 : The hybrid automaton for the corresponding HModel of the question is addressed in sect. 4.2.

Figure 3.6 : The hybrid automaton for the corresponding HModel of the question is addressed in sect. 4.3.

Figure 3.7 : The hybrid automaton for the corresponding HModel of the question addressed in sect 4.4

Figure 3.8 : The hybrid automaton for the corresponding HModel of the question addressed in sect. 4.5.

Round	constr	makespan	dwell-diff	diff-cost τ
1	$\leq 50$	32	$-$	$-$
2	$<32$	31.5	{ $moving,\ 0.5$ }	$-0.5$
3	$<31$	18	{ $moving,\ 13.5$ }	$-13.5$
4	$<18$	17.5	{ $moving,\ 0.5$ }	$-0.5$
5	$<17$	14	{ $moving,\ 3.5$ }	$-3.5$
6	$<14$	13.5	{ $moving,\ 0.5$ }	$-0.5$

Table 3.1 : The makespan of the plan for each re-plan iteration

Figure 3.9 : The hybrid automaton for the corresponding HModel of the question addressed in sect. 4.7.

Figure 3.10 : The hybrid automaton for the corresponding HModel for question 8.

Q. No.	Rem	Add	Com	Dwell-diff	DC τ	DC l	Remark
3.3.1	0	2	3	{ moving , 20}	-20	2	HPlan has a shorter makespan but a
							longer plan in terms of applied actions.
							The original plan is better.
3.3.2	1	1	2	{ moving , 14}	-14	0	The original plan is not optimal
							with respect to the duration of the plan.
							The HPlan is better.

Table 3.2 : A brief summary of the contrastive explanations generated for the user questions discussed above.

BM

Ins

PL

Dur

Len

QN

H-dur

H-len

CE metrics

CM

Time

H-time

Mem

H-mem

HQ

DC τ

DC l

(in sec)

(in MB)

Q1

12

6

-20

2

12

0.046

<

1

\checkmark

Q2

18

4

-14

0

1

0.024

<

1

\times

Q3

41.5

4

9.5

0

4

0.036

<

1

\checkmark

SM

32

4

Q4

RO

1

0.027

RO

<

1

RO

\checkmark

Q5

RO

3

RO

\checkmark

Table 3.3 : BM represents the problem domains in PDDL+,and Ins represents the problem instances of a domain. PL reports the hybrid system planner chosen for solving the instances, where SM, EN, and UP represent SMTPlan+ , ENHSP , and UPMurphi , respectively. Dur and Len represent the original plan-duration and plan length for a problem instance, QN represents the set of contrastive questions presented in Section 3.3 , H-dur and H-len represent the plan-duration and the plan-length of the hypothetical plan HPlan . DC τ and DC l represent the plan-duration difference and the plan-length difference of the HPlan with the original plan, respectively; these are the contrastive explanation (CE) metrics illustrated in Def 3.2.6 . CM reports the number of constraint modifications that are made in the domain (inclusive of constraint addition and deletion). Time and H-time represent the plan generation time whereas Mem and H-mem report the memory usages for the original plan and the HPlan , respectively. HQ represents an evaluation on the quality of the HPlan against the original plan.

Figure 3.11 : Scatter graph comparing the HPlan generation time over the original plan. OP represents the original plan whereas QN1 , QN2 , QN3 , QN4 , QN5 , QN7 and QN8 represent the HPlans generated against the compilations for the contrastive questions discussed in Sec. 3.3.1 , 3.3.2 , 3.3.3 , 3.3.4 , 3.3.5 , 3.3.7 and 3.3.8 , respectively.

Figure 3.12 : Scatter graph comparing the memory usages by the planner for the generation of HPlans and the original plan. OP represents the original plan whereas QN1 , QN2 , QN3 , QN4 , QN5 , QN7 and QN8 represent the HPlan corresponding to the contrastive questions addressed in Section 3.3.1 , 3.3.2 , 3.3.3 , 3.3.4 , 3.3.5 , 3.3.7 and 3.3.8 , respectively.

prob_ins	bound on plan-depth (k)	time (sec)	satisfiability
Sec. 3.3.4	10	0.288	UNSAT
Sec. 3.3.4	20	1.277	UNSAT
Sec. 3.3.5	10	541.423	UNSAT
Sec. 3.3.5	13	4010.524	UNSAT
Sec. 3.3.8	10	1.931	UNSAT
Sec. 3.3.8	20	8.152	UNSAT

Table 3.4 : Bounded reachability analysis of the no-plan-models for a given

\delta

perturbation of 0.01.

Figure 4.1 : Tool Workflow

Figure 4.3 : A snapshot of the tool’s GUI

Figure 4.4 : Binding templatized question with instances.

Figure 4.5 : An HPlan generated by SMTPlan+ according to the contrastive question.

				HModel	Best Contrastive
Benchmark	Q No.	SMTPlan+	ENHSP	Compilation Time	Plan Time
	q1	0.090s	0.842s	0.038s	1m2.396s
	q2	0.059s	0.520s	0.026s	1m28.344s
Car	q3	0.041s	0.384s	0.029s	0m51.703s
domain	q4	NP	NP	0.041s	NP
domain	q5	0.036s	0.492s	0.092s	0m52.123s

Table 4.1 : Table depicting the mean response time of our tool to each of the seven contrastive questions in the car and the generator-events domain. Q. No. is the contrastive question from the set of questions in Section 4.1 . The columns SMTPlan+ and ENHSP show the time taken by these planners to generate a plan. The column HModel Compilation Time shows the time taken to construct the Hmodel, and Best Contrastive Plan Time reports the time to find the best contrastive plan by iterative re-modeling with Bisection. NP denotes no plan produced within a given time-bound. NA denotes not applicable.

Figure 5.1 : The human and the agent view of the warehouse environment is depicted. Each cell is associated with an identifier shown in the top-left corner of the cell. The Blue dotted line represents an expected plan by a human under its knowledge of the warehouse. Our explanation algorithm examines this plan in the agents’ view of the world and detects the presence of an obstacle in cell number 20. This knowledge is reported to the user as an explanation of the infeasibility of the plan. The Green dashed line represents a candidate plan in the human model when abstracting its continuous dynamics. This plan is refuted by our algorithm when the feasibility of the path is checked against the continuous dynamics of the human model.

Figure 5.2 : Infeasibility of the plan explained by continuous dynamics, particularly the higher charge depletion rate at orange cells

Figure 5.3 : The HA model for the warehouse automation problem, where locations represent the corresponding cells shown in Figure 5.1 . The automaton provided here is a part of the warehouse automation domain.

Figure 5.4 : The flow diagram of our model reconciliation framework

				Trans		No. of (in HM)		Paths	Invalid	IIS	Time	Mem
Benchmark	Ins	Dep	Loc	HM	AM	paths	inf. paths	replayed	edges	segs	(in sec)	(in MB)
		7				3	0	3	0	3	0.96	64.9
	Prob01	10	24	56	50	64	6	58	1	55	2.90	77.6
		15				98862	21352	77510	3	41513	13119.16	1993.7
Warehouse		7				2	2	0	1	0	1.20	71.1
automation	Prob02	10	24	56	50	38	32	6	3	3	1.48	70.3

Table 5.1 : Results on the warehouse automation and water-level monitoring systems. HM and AM represent Human Model and Agent Model, respectively.

Benchmark	Ins	Depth	Avg time
Benchmark	Ins	Depth	(in sec)
	Prob01	7	0.32
		10	0.045
		15	0.132
Warehouse	Prob02	7	0.6
automation		10	0.038

Table 5.2 : Average explanation generation time.

Figure 6.1 : The rover domain is depicted. Initially, the rover is at cell 11. Mountains and craters are impassable regions of the terrain, such as cells 7, 12, etc. The rover needs to collect soil samples from cell 1 and rock samples from cell 24. The base station is at cell 25. The up-slope areas in the terrain are shown in orange. The inevitable waypoints in the domain are cells

w1

to

w8

marked in blue.

Figure 6.2 : A hybrid automaton model of the planetary rover domain (partially shown).

Figure 6.3 : Proposed Explanation Framework.

Figure 6.4 : All runs of valid plans from the initial set to the goal set must pass through the blue doorway. We envision the blue region as an inevitable waypoint to the planning problem.

Figure 6.5 : A depiction of a graph of a

\mathcal{H}

. Let S and D be the source and the goal locations in a planning problem

\Pi

. Every path from S to D visits locations A and B in sequence. Thus, S-A-B-D is the LCS of paths in PS(

\Pi

). Clearly, if a valid run of a plan exists in the

\mathcal{H}

, the run must visit the invariants of S, A, B, and D sequentially.

Benchmarks		#Locs	#Trans	Depth	$\mid$ PS( $\Pi$ ) $\mid$	$\lvert\text{Y}^{<}\rvert$	#Feas.	Exp( $\Pi$ )	Time	Memory
							wps		(in sec)	(in MB)
Planetary		25	40	15	244	10	6	Loc13	0.47	11.5
rover (PR)				20	20477				3.60	447.3
City		10	25	10	468	4	2	Loc7	0.73	10.1
route (CR)				15	92172				5.93	1075.8
	6x4	24	50	10	36	6	4	Loc17	1.57	8.8

Table 6.1 : Explanation generation on unsolvable planning problem instances.

Benchmarks		Depth	Time (in secs)			AT
Benchmarks		Depth	(a) PE	(b) Finding Y <	(c) RA	AT
PR		15	0.03	0.01	0.43	0.47
PR		20	1.99	1.14	0.47	3.60
CR		10	0.03	0.01	0.69	0.73
CR		15	4.72	0.23	0.98	5.93
WA	6x4	10	0.01	0.01	1.54	1.57

Table 6.2 : Performance analysis of our framework. PE indicates Path-exploration time, RA indicates Reachability analysis time, and AT indicates Accumulative Time = (a) + (b) + (c).

Figure 6.6 : Illustration of results in the example scenarios.

Figure 6.7 : The city route network is depicted. Each node represents the important junctures of the city. The blue-colored routes represent both-way transportation between junctures. The green-colored routes represent one-way traffic. Initially, the car is at juncture A (shown as the green-colored node). The junctures I (yellow-colored), H (red-colored), and J (blue-colored) are the destinations of three different planning problems of the domain. The orange-colored nodes in the figure are the waypoints that appear in every source-to-destination path for a planning problem of A to H.

Figure 6.8 : Warehouse automation domain.

Explainable Planning for Hybrid Systems

Abstract

Figures & tables

Explainable Artificial Intelligence

Self-Explainability in Self-Adaptive and Self-Organising Systems: Status and Research Directions

Exploring Plan Space through Conversation: An Agentic Framework for LLM-Mediated Explanations in Planning

Mind the Prompt: Self-adaptive Generation of Task Plan Explanations via LLMs

Abstract

Explainable Artificial Intelligence

Explore similar work

Self-Explainability in Self-Adaptive and Self-Organising Systems: Status and Research Directions

Exploring Plan Space through Conversation: An Agentic Framework for LLM-Mediated Explanations in Planning

Mind the Prompt: Self-adaptive Generation of Task Plan Explanations via LLMs