Out of Sight But Not Out of Mind: An Answer Set Programming Based Online Abduction Framework for Visual Sensemaking in Autonomous Driving

1 Motivation

Autonomous driving research has received enormous academic & industrial interest in recent years. This surge has coincided with (and been driven by) advances in deep learning based computer vision research. Although deep learning based vision & control has (arguably) been successful for self-driving vehicles, we posit that there is a clear need and tremendous potential for hybrid visual sensemaking solutions (integrating vision and semantics) towards fulfilling essential legal and ethical responsibilities involving explainability, human-centred AI, and industrial standardisation (e.g, pertaining to representation, realisation of rules and norms).

Autonomous Driving: "Standardisation &Regulation"

As the self-driving vehicle industry develops, it will be necessary -e.g., similar to sectors such as medical computing, computer aided design- to have an articulation and community consensus on aspects such as representation, interoperability, human-centred performance benchmarks, and data archival & retrieval mechanisms. 1 In spite of major investments in self-driving vehicle research, issues related to human-centred'ness, human collaboration, and standardisation have been barely addressed, with the current focus in driving research primarily being on two basic considerations: how fast to drive, and which way and how much to steer. This is necessary, but inadequate if autonomous vehicles are to become commonplace and function with humans. Ethically driven standardisation and regulation will require addressing challenges in semantic visual interpretation, natural / multimodal human-machine interaction, high-level data analytics (e.g., for post hoc diagnostics, dispute settlement) etc. This will necessitate -amongst other things- human-centred qualitative benchmarks and multifaceted hybrid AI solutions.

1 Within autonomous driving, the need for standardisation and ethical regulation has most recently garnered interest internationally, e.g., with the Federal Ministry of Transport and Digital Infrastruc-

Visual Sensemaking Needs Both "Vision & Semantics"

We demonstrate the significance of semantically-driven methods rooted in knowledge representation and reasoning (KR) in addressing research questions pertaining to explainability and human-centred AI particularly from the viewpoint of sensemaking of dynamic visual imagery. Consider the occlusion scenario in Fig. 1:

Car (c) is in-front; during this time, person (p) is on a bicycle (b) and positioned front-right of c and moving-forward. Car c turns-right, during which the bicyclist < p, b > is not visible. Subsequently, bicyclist < p, b > reappears.

The occlusion scenario indicates several challenges concerning aspects such as: identity maintenance, making default assumptions, computing counterfactuals, projection, and interpolation of missing information (e.g., what could be hypoth-

ture in Germany taking a lead in eliciting 20 key propositions (with legal implications) for the fulfilment of ethical commitments for automated and connected driving systems [BMVI, 2018].

esised about bicyclist < p, b > when it is occluded; how can this hypothesis enable in planning an immediate next step). Addressing such challenges -be it realtime or post-hoc- in view of human-centred AI concerns pertaining to ethics, explainability and regulation requires a systematic integration of Semantics and Vision, i.e., robust commonsense representation & inference about spacetime dynamics on the one hand, and powerful low-level visual computing capabilities, e.g., pertaining to object detection and tracking on the other.

Key Contributions. We develop a general and systematic declarative visual sensemaking method capable of online abduction: realtime, incremental, commonsense questionanswering and belief maintenance over dynamic visuospatial imagery. Supported are (1-3): (1). human-centric representations semantically rooted in spatio-linguistic primitives as they occur in natural language [Bhatt et al., 2013; Mani and Pustejovsky, 2012]; (2). driven by Answer Set Programming (ASP) [Brewka et al., 2011], the ability to abductively compute commonsense interpretations and explanations in a range of (a)typical everyday driving situations, e.g., concerning safety-critical decision-making; (3). online performance of the overall framework modularly integrating high-level commonsense reasoning and state of the art lowlevel visual computing for practical application in real world settings. We present the formal framework & its implementation, and demo & empirically evaluate with community established real-world datasets and benchmarks, namely: KITTIMOD [Geiger et al., 2012] and MOT [Milan et al., 2016].

2 Visual Sensemaking: A General Method Driven by ASP

Our proposed framework, in essence, jointly solves the problem of assignment of detections to tracks and explaining overall scene dynamics (e.g. appearance, disappearance) in terms of high-level events within an online integrated lowlevel visual computing and high level abductive reasoning framework (Fig. 2). Rooted in answer set programming, the framework is general, modular, and designed for integration as a reasoning engine within (hybrid) architectures designed for real-time decision-making and control where visual perception is needed as one of the several components. In such large scale AI systems the declarative model of the scene dynamics resulting from the presented framework can be used for semantic Q/A, inference etc. to support decision-making.

2.1 Space, Motion, Objects, Events

Reasoning about dynamics is based on high-level representations of objects and their respective motion & mutual interactions in spacetime. Ontological primitives for commonsense reasoning about spacetime (Σst) and dynamics (Σdyn) are:

Σst: domain-objects O = {o1, ..., on} represent the visual elements in the scene, e.g., people, cars, cyclists; elements in O are geometrically interpreted as spatial entities E= {ε1, ..., εn}; spatial entities E may be regarded as points, line-segments or (axis-aligned) rectangles based on their spatial properties (and a particular reasoning task at hand). The temporal dimension is represented by time points T = {t1, ..., tn}. MT oi = (εts , ..., εte ) represents the motion track of a single object oi, where ts and te denote the start and end time of the track and εts to εte denotes the spatial entity (E) -e.g., the axis-aligned bounding box-corresponding to the object oi at time points ts to te. The spatial configuration of the scene and changes within it are characterised based on the qualitative spatiotemporal relationships (R) between the domain objects. For the running and demo examples of this paper, positional relations on axis-aligned rectangles based on the rectangle algebra (RA) [Balbiani et al., 1999] suffice; RA uses the relations of Interval Algebra (IA) [Allen, 1983] RIA ≡ {before, after, during, contains, starts, started by, finishes, finished by, overlaps, overlapped by, meets, met by, equal} to relate two objects by the interval relations projected along each dimension separately (e.g., horizontal and vertical dimensions).

Σdyn: The set of fluents Φ = {φ1, ..., φn} and events Θ = {θ1, ..., θn} respectively characterise the dynamic properties of the objects in the scene and high-level abducibles (Table

Algorithm 1: Online Abduction(V, Σ)

Data: Visual imagery (V), and background knowledge Σ ≡def Σdyn ∪ Σst Result: Visual Explanations (EXP) (Refer Fig. 3) 1 MT ←∅, Hevents ←∅ 2 for t ∈ T do 3 VOt ← observe(Vt) 4 Pt ←∅,MLt ←∅ 5 for trk ∈MT t-1 do 6 ptrk ← kalman predict(trk) 7 Pt ← Pt ∪ ptrk 8 for obs ∈ VOt do 9 mltrk,obs ← calc IoU(ptrk, obs) 10 MLt ← MLt ∪ mltrk,obs 11 abduce(<Hassign t , Hevents t >) (Refer Step 2) 12 Hevents ←Hevents ∪Hevents t 13 MT t ← update(MT t-1, VOt,Hassign) 14 return EXP ← <Hevents ,MT >

1). For reasoning about dynamics (with <Φ, Θ>), we use a variant of event calculus as per [Ma et al., 2014; Miller et al., 2013]; in particular, for examples of this paper, the functional event calculus fragment (Σdyn) of Ma et al. [2014] suffices: main axioms relevant here pertain to occurs-at(θ, t) denoting that an event occurred at time t and holds-at(φ, v, t) denoting that v holds for a fluent φ at time t. 2

2.2 Tracking as Abduction

Scene dynamics are tracked using a detect and track approach: we tightly integrate low-level visual computing (for detecting scene elements) with high-level ASP-based abduction to solve the assignment of observations to object tracks in an incremental manner. For each time point t we generate a problem specification consisting of the object tracks and visual observations and use ASP to abductively solve the corresponding assignment problem incorporating the ontological structure of the domain / data (abstracted with Σ). Steps 1-3 (Alg. 1 & Fig. 3) are as follows:

Step 1. Formulating the Problem Specification The ASP problem specification for each time point t is given by the tuple < VOt,Pt,MLt > and the sequence of events (Hevents ) before time point t.

Visual Observations (VOt): Scene elements derived directly from the visual input data are represented as spatial entities E, i.e., VOt = {εobs1 , ..., εobsn } is the set of observations at time t (Fig. 3). For the examples and empirical evaluation in this paper (Sec. 3) we focus on Obstacle / Object Detections - detecting cars, pedestrians, cyclists, traffic lights etc using YOLOv3 [Redmon and Farhadi, 2018]. Further we generate scene context using Semantic Segementation - segmenting the road, sidewalk, buildings, cars, people, trees, etc. using DeepLabv3+ [Chen et al., 2018], and Lane Detection - estimating lane markings, to detect lanes on the road, using SCNN [Pan et al., 2018]. Type and confidence score for each observation is given by typeobsi and confobsi .

2 ASP encoding of the domain independent axioms of the Functional Event Calculus (FEC) used as per: https://www.ucl.ac.uk/infostudies/efec/fec.lp

Movement Prediction (Pt): For each track trki changes in position and size are predicted using kalman filters; this results in an estimate of the spatial entity ε for the next timepoint t of each motion track Pt = {εtrk1 , ..., εtrkn }.

Matching Likelihood (MLt): For each pair of tracks and observations εtrki and εobsj , where εtrki ∈ Pt and εobsj ∈ VOt, we compute the likelihood MLt = {mltrk1,obs1 , ...,mltrki,obsj } that εobsj belongs to εtrki . The intersection over union (IoU) provides a measure for the amount of overlap between the spatial entities εobsj and εtrki .

Step 2. Abduction based Association Following perception as logical abduction most directly in the sense of Shanahan [2005], we define the task of abducing visual explanations as finding an association (Hassign t ) of observed scene

I MATCHING TRACKS AND DETECTIONS

elements (VOt) to the motion tracks of objects (MT ) given by the predictions Pt, together with a high-level explanation (Hevents t ), such that [Hassign t ∧ Hevents t ] is consistent with the background knowledge and the previously abduced event sequence Hevents , and entails the perceived scene given by < VOt, Pt,MLt >: Σ ∧ Hevents ∧ [Hassign t ∧Hevents t ] |= VOt ∧Pt ∧MLt where Hassign t consists of the assignment of detections to object tracks, and Hevents t consists of the high-level events Θ explaining the assignments. We associate objects and observations by finding the best match between observations VOt and predicted object tracks Pt. Towards this we use choice rules [Gebser et al., 2014] (i.e., one of the heads of the rule has to be in the stable model) for εobsj and εtrki , generating all possible assignments in terms of assignment actions: assign, start, end, halt, resume, ignore det, ignore trk, and then maximising the matching likelihood mltrki,obsj between pairs of spatial entities for matched observations εobsj and predicted track region εtrki (See Step 3). I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... For each assignment action we define integrity constraints 3 that restrict the set of answers generated by the choice rules, e.g., the following constraints are applied to assigning an observation εobsj to a track trki, applying thresholds on the IoUtrki,obsj and the confidence of the observation confobsj , further we define that the type of the observation has to match the type of the track it is assigned to: I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. Abducible high-level events guide association and serve as explanations for object dynamics. For the length of this paper, we restrict to high-level visuo-spatial abducibles pertaining to object persistence and visibility (Table 1): (1). Occlusion: Objects can disappear or reappear as result of occlusion with other objects; (2). Noise and Missing Observation: (Missing-)observations can be the result of faulty detections. Lets take the case of occlusion: functional fluent visibility could be denoted fully visible, partially occluded or fully occluded: I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). We define the event hides behind/2, stating that an object hides behind another object by defining the conditions 3 Integrity constraints restrict the answer set by eliminating stable models where the body is satisfied. EVENTS Description hides behind(Trk1,Trk2) Trk1 hides behind Trk2. unhides from behind(Trk1,Trk2) Trk1 unhides from behind Trk2 . missing detections(Trk) Missing detections in Trk. FLUENTS Values Description hidden by(Trk1,Trk2) {true;false} Trk1 is hidden by Trk2. visibility(Trk) {fully visible; partially occluded; fully occluded} Visibility state of Trk. Table 1: Events and Fluents Explaining (Dis)Appearance that have to hold for the event to possibly occur, and the effects the occurrence of the event has on the properties of the objects, i.e., the value of the visibility fluent changes to fully occluded. 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, anticipate(unhides_from_behind(Trk1, _), T), position(in_front, interpolated_pos(Trk1, T)). For abducing the occurrence of an event we use choice rules that connect the event with assignment actions, e.g., a track getting halted may be explained by the event that the track hides behind another track. I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, anticipate(unhides_from_behind(Trk1, _), T), position(in_front, interpolated_pos(Trk1, T)). Step 3. Finding the Optimal Hypothesis To ensure an optimal assignment, we use ASP based optimization to maximize the matching likelihood between matched pairs of tracks and detections. Towards this, we first define the matching likelihood based on the Intersection over Union (IoU) between the observations and the predicted boxes for each track as described in [Bewley et al., 2016]: I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, anticipate(unhides_from_behind(Trk1, _), T), position(in_front, interpolated_pos(Trk1, T)). We then maximize the matching likelihood for all assignments, using the build in maximize statement: I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, To find the best set of hypotheses with respect to the observations, we minimize the occurrence of certain events and association actions, e.g., the following optimization statements minimize starting and ending tracks; the resulting assignment is then used to update the motion tracks accordingly. I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. It is important here to note that: (1). by jointly abducing the object dynamics and high-level events we can impose constraints on the assignment of detections to tracks, i.e., an assignment is only possible if we can find an explanation supporting the assignment; and (2). the likelihood that an event 1882

box2d(trk_3, 660, 460, 134, 102). ...

... box2d(trk_41, 631, 471, 40, 47). ...

... occurs_at(hides_behind(trk_41,trk_3),179)) ...

hides behind unhides from behind t220 fully_occluded anticipated reappearance t180 t160 t200 Figure 4: Abducing Occlusion to Anticipate Reappearance anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, anticipate(unhides_from_behind(Trk1, _), T), position(in_front, interpolated_pos(Trk1, T)).

Empirical Evaluation For online sensemaking, evaluation focusses on accuracy of abduced motion tracks, real-time performance, and the tradeoff between performance and accuracy. Our evaluation uses the KITTI object tracking dataset [Geiger et al., 2012], which is a community established benchmark dataset for autonomous cars: it consists of 21 training and 29 test scenes, and provides accurate track annotations for 8 object classes (e.g., car, pedestrian, van, cyclist). We also evaluate tracking results using the more general cross-domain Multi-Object Tracking (MOT) dataset [Milan et al., 2016] established as part of the MOT Challenge; it consists of 7 training and 7 test scenes which are highly unconstrained videos filmed with both static and moving cameras. We evaluate on the available groundtruth for training scenes of both KITTI using YOLOv3 detections, and MOT17 using the provided faster RCNN detections.

For evaluating object tracking we consider accuracy (MOTA) and precision (MOTP) of abduced object tracks following the Clear MOT [Bernardin and Stiefelhagen, 2008] evaluation schema. Results (Table 3) show that jointly abducing high-level object interactions together with low-level scene dynamics increases the accuracy of the object tracks, i.e, we consistently observe an improvement of about 5%, from 45.72% to 50.5% for cars and 28.71% to 32.57% for pedestrians on KITTI, and from 41.4% to 46.2% on MOT.

Online performance and scalability of online abduction is evaluated with respect to its real-time capabilities. 4 (1). We compare the time & accuracy of online abduction for state of the art (real-time) detection methods: YOLOv3, SSD [Liu et al., 2016], and Faster RCNN [Ren et al., 2015] (Fig. 5). (2). We evaluate scalability of the ASP based abduction on a synthetic dataset with controlled number of tracks and % of overlapping tracks per frame. Results (Fig. 5) show that online abduction can perform with above 30 frames per second for scenes with up to 10 highly overlapping object tracks, and more than 50 tracks with 1fps (for the sake of testing, it is worth noting that even for 100 objects per frame it only takes about an average of 4 secs per frame). Importantly, for realistic scenes such as in the KITTI dataset, abduction runs realtime at 33.9fps using YOLOv3, and 46.7 using SSD with lower accuracy but providing good precision.

Discussion of Empirical Results Results show that integrating high-level abduction and object tracking improves the

Situation Objects Description HIDDEN ENTITY entity, object traffic participant hidden by obstacle REDUCED VISIBILITY object visibility reduced by object in front. SUDDEN STOP vehical vehicle in front stopping suddenly BLOCKED LANE lane, object lane of the road is blocked by an object. Table 2: Safety-Critical Situations occurs guides the assignments of observations to tracks. Instead of independently tracking objects and interpreting the interactions, this yields to event sequences that are consistent with the abduced object tracks, and noise in the observations is reduced (See evaluation in Sec. 3). 3 Application &Evaluation We demonstrate applicability towards identifying and interpreting safety-critical situations (e.g., Table 2); these encompass those scenarios where interpretation of spacetime dynamics, driving behaviour, environmental characteristics is necessary to anticipate and avoid potential dangers. Reasoning about Hidden Entities Consider the situation of Fig. 4: a car gets occluded by another car turning left and reappears in front of the autonomous vehicle. Using online abduction for abducing high-level interactions of scene objects we can hypothesize that the car got occluded and anticipate its reappearance based on the perceived scene dynamics. The following shows data and abduced events. start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... trk(trk_41, car). trk_state(trk_41, active). ... box2d(trk_3, 660, 460, 134, 102). ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, anticipate(unhides_from_behind(Trk1, _), T), position(in_front, interpolated_pos(Trk1, T)). We define a rule stating that a hidden object may unhide from behind the object it is hidden by and anticipate the time point t based on the object movement as follows: 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, anticipate(unhides_from_behind(Trk1, _), T), position(in_front, interpolated_pos(Trk1, T)). We then interpolate the objects position at time point t to predict where the object may reappear. I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, anticipate(unhides_from_behind(Trk1, _), T), For the occluded car in our example we get the following prediction for time t and position x, y: I MATCHING TRACKS AND DETECTIONS 1{ assign(Trk, Det): det(Det, _, _); end(Trk); ignore_trk(Trk); halt(Trk); resume(Trk, Det): det(Det, _, _) }1 :- trk(Trk, _). 1{ assign(Trk, Det): trk(Trk, _); start(Det); ignore_det(Det); resume(Trk, Det): trk(Trk, _). }1 :- det(Det, _, _). I INTEGRITY CONSTRAINTS ON MATCHING :- assign(Trk, Det), not assignment_constraints(Trk, Det). assignment_constraints(Trk, Det) :- trk(Trk, Trk_Type), trk_state(Trk, active), det(Det, Det_Type, Conf), Conf > conf_thresh_assign, match_type(Trk_Type, Det_Type), iou(Trk, Det, IOU), IOU > iou_thresh. I VISIBILITY - FLUENT AND POSSIBLE VALUES fluent(visibility(Trk)) :- trk(Trk, _). possVal(visibility(Trk), fully_visible) :- trk(Trk, _). possVal(visibility(Trk), partially_visible) :- trk(Trk,_). possVal(visibility(Trk), not_visible) :- trk(Trk, _). I OCCLUSION - EVENT, EFFECTS AND (SPATIAL) CONSTRAINTS event(hides_behind(Trk1,Trk2)) :- trk(Trk1,_),trk(Trk2,_). causesValue(hides_behind(Trk1, Trk2), visibility(Trk1), not_visible, T) :- trk(Trk1,_), trk(Trk2,_), time(T). :- occurs_at(hides_behind(Trk1, Trk2), curr_time), trk(Trk1,_), trk(Trk2,_), not position(overlapping_top, Trk1, Trk2). I GENERATING HYPOTHESES ON EVENTS 1{ occurs_at(hides_behind(Trk, Trk2), curr_time): trk(Trk2,_); ... }1 :- halt(Trk). I ASSIGNMENT LIKELIHOOD assignement_prob(Trk, Det, IOU) :- det(Det, _, _), trk(Trk, _), iou(Trk, Det, IOU). I MAXIMIZING ASSIGNMENT LIKELIHOOD #maximize {(Prob)@1,Trk,Det : assign(Trk, Det), assignment_prob(Trk, Det, Prob)}. I OPTIMIZE EVENT AND ASSOCIATION COSTS #minimize {5@2,Trk: end(Trk)}. #minimize {5@2,Det: start(Det)}. trk(trk_3, car). trk_state(trk_3, active). ... ... trk(trk_41, car).trk_state(trk_41, active). ... ... det(det_1, car, 98). ... box2d(trk_3, 660, 460, 134, 102). ... ... box2d(trk_41, 631, 471, 40, 47). ... ... occurs_at(hides_behind(trk_41,trk_3),179)) ... anticipate(unhides_from_behind(Trk1, Trk2), T) :- time(T), curr_time < T, holds_at(hidden_by(Trk1, Trk2), curr_time), topology(proper_part, Trk1, Trk2), movement(moves_out_of, Trk1, Trk2, T). point2d(interpolated_position(Trk, T), PosX, PosY) :- time(T), curr_time < T, T1 = T-curr_time, box2d(Trk1, X, Y,_,_), trk_mov(Trk1, MovX, MovY), PosX = X+MovX*T1, PosY = Y+MovX*T1. anticipate(unhides_from_behind(trk_41, trk_2), 202) point2d(interpolated_position(trk_41, 202), 738, 495) Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

position(in_front, interpolated_pos(Trk1, T)). warning(hidden_entity_in_front(Trk1, T)) :- time(T), T-curr_time < anticipation_threshold, anticipate(unhides_from_behind(Trk1, _), T), position(in_front, interpolated_pos(Trk1, T)). Based on this prediction we can then define a rule that gives a warning if a hidden entity may reappear in front of the vehicle, which could be used by the control mechanism, e.g., to adapt driving and slow down in order to keep safe distance:

4 Evaluation using a dedicated Intel Core i7-6850K 3.6GHz 6Core Processor, 64GB RAM, and a NVIDIA Titan V GPU 12GB.

resulting object tracks and reduce the noise in the visual observations. For the case of online visual sense-making, ASP based abduction provides the required performance: even though the complexity of ASP based abduction increases quickly, with large numbers of tracked objects the framework can track up to 20 objects simultaneously with 30fps and achieve real-time performance on the KITTI benchmark dataset. It is also important to note that the tracking approach in this paper is based on tracking by detection using a naive measure, i.e, the IoU (Sec. 2.2; Step 1), to associate observations and tracks, and it is not using any visual information in the prediction or association step. Naturally, this results in a lower accuracy, in particular when used with noisy detections and when tracking fast moving objects in a benchmark dataset such as KITTI. That said, due to the modularity of the implemented framework, extensions with different methods for predicting motion (e.g., using particle filters or optical flow based prediction) are straightforward: i.e., improving tracking is not the aim of our research.

4 RelatedWork

Answer Set Programming is now widely used as an underlying knowledge representation language and robust methodology for non-monotonic reasoning [Brewka et al., 2011; Gebser et al., 2012]. With ASP as a foundation, and driven by semantics, commonsense and explainability [Davis and Marcus, 2015], this research aims to bridge the gap between high-level formalisms for logical abduction and low-level visual processing by tightly integrating semantic abstractions of space-change with their underlying numerical representations. Within KR, the significance of high-level (abductive)

explanations in a range of contexts is well-established: planning & process recognition [Kautz, 1991], vision & abduction [Shanahan, 2005], probabilistic abduction [Blythe et al., 2011], reasoning about spatio-temporal dynamics [Bhatt and Loke, 2008], reasoning about continuous spacetime change [Muller, 1998; Hazarika and Cohn, 2002] etc. Dubba et al. [2015] uses abductive reasoning in an inductive-abductive loop within inductive logic programming (ILP). Aditya et al. [2015] formalise general rules for image interpretation with ASP. Similarly motivated to this research is [Suchan et al., 2018], which uses a two-step approach (with one huge problem specification), first tracking and then explaining (and fixing) tracking errors; such an approach is not runtime / realtime capable. In computer vision research there has recently been an interest to synergise with cognitively motivated methods; in particular, e.g., for perceptual grounding and inference [Yu et al., 2015], and combining video analysis with textual information for understanding events and answering queries about video data [Tu et al., 2014].

5 Conclusion &Outlook

We develop a novel abduction-driven online (i.e., realtime, incremental) visual sensemaking framework: general, systematically formalised, modular and fully implemented. Integrating robust state-of-the-art methods in knowledge representation and computer vision, the framework has been evaluated and demonstrated with established benchmarks. We highlight application prospects of semantic vision for autonomous driving, a domain of emerging and long-term significance. Specialised commonsense theories (e.g., about multi-sensory integration and multi-agent belief merging, contextual knowledge) may be incorporated based on requirements. Our ongoing focus is to develop a novel dataset emphasising semantics and (commonsense) explainability; this is driven by mixedmethods research -AI, Psychology, HCI- for the study of driving behaviour in low-speed, complex urban environments with unstructured traffic. Such interdisciplinary studies are needed to better appreciate the complexity and spectrum of varied human-centred challenges in autonomous driving, and demonstrate the significance of integrated vision and semantics solutions in those contexts.

Acknowledgements

Partial funding by the German Research Foundation (DFG) via the CRC 1320 EASE - Everyday Activity Science and Engineering" (www.ease-crc.org), Project P3: Spatial Reasoning in Everyday Activity is acknowledged.