EAGER: Robust Reasoning using a Geometric Approach to SAT and PSAT

这个迫切的项目的首要目标是为自主代理开发高效和可靠的方法，以制定其在复杂情况下的安全操作计划。例如，城市地区用于包裹递送的大规模无人机系统的发展依赖于这样的能力。根本问题是确定在特定情况下是否有可行的解决办法；目前这一问题的复杂性太高，不能保证能够找到解决办法。该研究团队正在开发一种复杂性较低的方法，并在人工智能中广泛应用。该项目从计算机科学中代表性不足的群体中聘请学生研究人员，并通过人工智能、计算理论和自主代理系统等课程将研究成果整合到课堂上。该项目为认知层面的代理规划提供了一种新的方法。其基本创新之处在于将可满足性问题转化为几何环境；具体地，将n元逻辑语句的模型视为n维超立方体的角点，内点为变量赋予概率。合取范式语句中的每个合取词减少了凸可行解区域。任何非空可行域都表示概率可满足性问题解的存在，也可以用多项式时间内的线性规划方法来寻找可满足性问题的解。要探索的具体方法包括：(1)使用障碍法对内点法进行修改，(2)在非欧几里德几何中寻找线性规划解，(3)对可行域应用随机旋转，以允许坐标投影确定是否存在解，以及(4)使用马尔科夫链蒙特卡洛来获得拐角附近的点。应用包括概率可满足性推理、自主代理的强化策略优化和概率时间逻辑。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The overarching goal of this EAGER project is to develop efficient and reliable methods for autonomous agents to produce plans for their safe operation in complex situations. For example, the development of large-scale unmanned aircraft system operation in urban areas for package delivery depends on such a capability. The fundamental issue is to determine if there is a viable solution in a specific situation; at the present time the complexity of this problem is too high to guarantee that a solution can be found. The team of researchers is developing a lower complexity approach with wide application in artificial intelligence. The project engages student researchers from underrepresented groups in computer science, and the research results are integrated into the classroom through courses like artificial intelligence, theory of computation, and autonomous agent systems.The project provides a new approach to agent planning at the cognitive level. The basic innovation is to convert the satisfiability problem into a geometric setting; in particular, the models of an n-variable logical sentence are viewed as the corners of an n-D hypercube, and interior points assign probabilities to the variables. Each conjunct in the conjunctive normal form sentence reduces the convex feasible solution region. Any non-empty feasible region indicates the existence of a solution to the probabilistic satisfiability problem and can also be probed with linear programming methods in polynomial time to seek an answer to the satisfiability problem. Particular approaches to be explored include: (1) modifications to the interior point method using barrier methods, (2) finding linear programming solutions in a non-Euclidean geometry, (3) applying random rotations to the feasible region to allow coordinate projects to determine if there is a solution, and (4) using Markov Chain Monte Carlo to get a point near a corner. Applications include probabilistic satisfiability inference, reinforcement policy optimization for autonomous agents, and probabilistic temporal logic.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.