Nondeterministic programming: Difference between revisions

Revision as of 20:27, 14 March 2022

Revision as of 08:05, 23 January 2023

Line 6:

One method of choice is embodied in [[backtracking]] systems (such as [[Amb (evaluator)|Amb]],<ref>{{Cite web|url=https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3.3|title=Structure and Interpretation of Computer Programs}}</ref> or unification in [[Prolog]]), in which some alternatives may "fail," causing the program to backtrack and try other alternatives. If all alternatives fail at a particular choice point, then an entire branch fails, and the program will backtrack further, to an older choice point. One complication is that, because any choice is tentative and may be remade, the system must be able to restore old program states by undoing side-effects caused by partially executing a branch that eventually failed.

Another method of choice is reinforcement learning, embodied in systems such as [[Alisp]].<ref>http://www.cs.berkeley.edu/~russell/papers/aaai02-alisp.pdf {{Barecite URLjournal|author1=David PDFAndre |author2=Stuart J. Russell|title=State abstraction for programmable reinforcement learning agents|journal=Eighteenth national conference on Artificial intelligence|date=MarchJuly 20222002|pages=119–125|doi=10.5555/777092.777114}}</ref> In such systems, rather than backtracking, the system keeps track of some measure of success and learns which choices often lead to success, and in which situations (both internal program state and environmental input may affect the choice). These systems are suitable for applications to [[robotics]] and other domains in which backtracking would involve attempting to undo actions performed in a dynamic environment, which may be difficult or impractical.

==See also==