BCI Control of Heuristic Search Algorithms

Abstract

The ability to develop Brain-Computer Interfaces (BCI) to Intelligent Systems would offer new perspectives in terms of human supervision of complex Artificial Intelligence (AI) systems, as well as supporting new types of applications. In this article, we introduce a basic mechanism for the control of heuristic search through fNIRS-based BCI. The rationale is that heuristic search is not only a basic AI mechanism but also one still at the heart of many different AI systems. We investigate how users' mental disposition can be harnessed to influence the performance of heuristic search algorithm through a mechanism of precision-complexity exchange. From a system perspective, we use weighted variants of the A* algorithm which have an ability to provide faster, albeit suboptimal solutions. We use recent results in affective BCI to capture a BCI signal, which is indicative of a compatible mental disposition in the user. It has been established that Prefrontal Cortex (PFC) asymmetry is strongly correlated to motivational dispositions and results anticipation, such as approach or even risk-taking, and that this asymmetry is amenable to Neurofeedback (NF) control. Since PFC asymmetry is accessible through fNIRS, we designed a BCI paradigm in which users vary their PFC asymmetry through NF during heuristic search tasks, resulting in faster solutions. This is achieved through mapping the PFC asymmetry value onto the dynamic weighting parameter of the weighted A* (WA*) algorithm. We illustrate this approach through two different experiments, one based on solving 8-puzzle configurations, and the other on path planning. In both experiments, subjects were able to speed up the computation of a solution through a reduction of search space in WA*. Our results establish the ability of subjects to intervene in heuristic search progression, with effects which are commensurate to their control of PFC asymmetry: this opens the way to new mechanisms for the implementation of hybrid cognitive systems.

Keywords: brain-computer interfaces (BCI); functional near-infrared spectroscopy (fNIRS); heuristic search; neurofeedback (NF); user interfaces.

Figure 1

Impact of dynamic weighting on the size of the 8-puzzle search space.

Figure 2

Experiment I: Rest, Neurofeedback (NF) and Count epochs.

Figure 3

Experiment I—Subjects equipped with an fNIRS sensor engage in a NF task whose visual display is a metaphor for the search space they are trying to reduce. Mapping between fNIRS signal and the WA* weighting coefficient is implemented via real-time statistical testing of prefrontal asymmetry. The weighting coefficient is only modified once, with several attempts in the early stages of the search process. Note that since each epoch (without the first 7 s, shown in gray) contained at least 66 observations (33 s with 2 Hz sampling frequency), we applied as threshold criterion the t critical value for p = 0.05 (two-tailed) with 65° of freedom, t_{crit (65)} = 2.00.

Figure 4

Experiment II: Count and NF epochs. Left-asymmetric increase in DL-Prefrontal Cortex (PFC) activity during NF was mapped to the width of the red cone, which was used as a visual metaphor (i.e., narrowing the beam of a searchlight) for supporting the search process.

Figure 5

Experiment II—Subjects equipped with an fNIRS sensor engage in a NF task whose visual display is this time the progression of the search process in path planning on a grid. The real-time mapping shown on the graph illustrates how increasing w values depends on positive up-regulation of asymmetry score. Unlike Experiment I, the weighting coefficient can be subject to successive dynamic increases during search. Examples: (1) shows a standard un-influenced solution path; (2) shows details of the cone visual feedback to the user’s positive input, matching to the acceleration of the search process, thus to a reduction of the search space (nodes unexplored on the right-hand side); and (3) shows the alternative solution produced by WA* under the subject’s influence.

Figure 6

Examples of average left and right oxygenated-hemoglobin (HbO) changes over time, as well as asymmetry, during two successful blocks (a, b) in Experiment I. Areas in gray represent the first 7 s of each epoch (i.e., the approximate delay of the hemodynamic response). Note that during the NF epoch, HbO increases bilaterally, with asymmetry to the left; during the Count epoch following NF, HbO decreases on both sides; during Rest, HbO further decreases towards baseline.

Figure 7

Experiment I: decrease of the number of the nodes expanded during the state-space search across successful NF epochs (total number of nodes explored without intervention is 34,400 for the 8-puzzle configuration used in the experiments).

Figure 8

Experiment II: number of nodes expanded during state-space search across successful NF epochs.

Figure 9

Distribution of w values across successful NF blocks (r = 0.895, p < 0.001).

Figure 10

Mean and standard error of fNIRS signal across all successful blocks in Experiment II for left (Red) and right (Blue) sides separately (left rises above right during NF epoch).