Application problems

We give some example application problems.  Authors of position papers may choose to use any or all of them, or use additional problems.

• Path planning --- finding a sequence of steps or configurations that moves an object from a starting configuration to an ending configuration and satisfies given constraints.  This is ubiquitous, and a classical example of a hard problem is the Traveling Salesman Problem (TSP) [1].

• Job scheduling --- finding a schedule that assigns each job to a machine with a starting time given constraints about the jobs, machines, and their placements.  This is also ubiquitous, with many variants, e.g., the Job Shop Scheduling Problem (JSSP) [2].

• Regulatory compliance --- checking and reasoning about complying to laws, regulations, policies, requirements, standards, and other rules that are set forth by governments, organizations, etc.  This is again everywhere.

An earlier example is the British Nationality Act 1981 [3].

A current example is the U.S. Federal Reserve's Regulation W for Transactions between member banks and their affiliates [4].

Countless applications require solving such problems. They often can be viewed using multiple lenses.  For example, a college student needs to plan for a set of courses to take each semester; this can also be viewed as a scheduling problem that assigns different courses to different semesters; it can also be viewed as compliance checking and reasoning against the course and graduation requirements.

Applications often also pose additional challenges like uncertainty, due to lacking information, imprecise information, conflicting information, etc. For example, the exact courses offered for future years may be uncertain, and the graduation requirements might even change.

Central issues to all these problems include:

1. How should the problem be expressed correctly and clearly 

   (in logic or formal specification languages and in natural languages)?

2. How should the problem be solved correctly and efficiently 

   (using any combination of methods and tools)?

These are the core of knowledge representation and reasoning.  Overall, how might a user iterate 1 and 2 above to arrive at desired solutions, taking advantages of all the languages and tools (LLMs and solvers included)?

References

[1] https://en.wikipedia.org/wiki/Travelling_salesman_problem (Last updated July 13, 2024)

[2] https://en.wikipedia.org/wiki/Job-shop_scheduling (Last updated July 16, 2024)

[3] https://www.legislation.gov.uk/ukpga/1981/61/pdfs/ukpga_19810061_en.pdf (Accessed July 31, 2024)

[4] https://www.ecfr.gov/current/title-12/chapter-II/subchapter-A/part-223 (Accessed July 31, 2024)

Acknowledgement

Thanks to Martin Gebser for bringing up the job scheduling problem, to Paul Fodor for reminding about the British Nationality Act 1981, and to Michael Kifer for the problem and reference to Regulation W.