Defining a Solution (four common classes of solutions: )

(17th-February-2020)

• Optimal solution

• An optimal solution to a problem is one that is the best solution according to some measure of solution quality. This measure is typically specified as an ordinal, where only the order matters. However, in some situations, such as when combining multiple criteria or when reasoning under uncertainty, you need a cardinal measure, where the relative magnitudes also matter. An example of an ordinal measure is for the robot to take out as much trash as possible.

• Satisficing solution

• Often an agent does not need the best solution to a problem but just needs some solution. A satisficing solution is one that is good enough according to some description of which solutions are adequate. A person may tell a robot that it must take all of trash out, or tell it to take out three items of trash.

• Approximately optimal solution

• One of the advantages of a cardinal measure of success is that it allows for approximations. An approximately optimal solution is one whose measure of quality is close to the best that could theoretically be obtained.

• Probable solution

• A probable solution is one that, even though it may not actually be a solution to the problem, is likely to be a solution. This is one way to approximate, in a precise manner, a satisficing solution. For example, in the case where the delivery robot could drop the trash or fail to pick it up when it attempts to, you may need the robot to be 80% sure that it has picked up three items of trash.