A key component of humans' striking creativity in solving problems is our ability to construct novel descriptions to help us characterize novel categories. Bongard problems, which challenge the problem solver to come up with a rule for distinguishing visual scenes that fall into two categories, provide an elegant test of this ability. Bongard problems are challenging for both human and machine category learners because only a handful of example scenes are presented for each category, and they often require the open-ended creation of new descriptions. A new sub-type of Bongard problem called Physical Bongard Problems (PBPs) is introduced, which require solvers to perceive and predict the physical spatial dynamics implicit in the depicted scenes. The PATHS (Perceiving And Testing Hypotheses on Structures) computational model which can solve many PBPs is presented, and compared to human performance on the same problems. PATHS and humans are similarly affected by the ordering of scenes within a PBP, with spatially and temporally juxtaposed scenes promoting category learning when they are similar and belong to different categories, or dissimilar and belong to the same category. The core theoretical commitments of PATHS which we believe to also exemplify human open-ended category learning are a) the continual perception of new scene descriptions over the course of category learning; b) the context-dependent nature of that perceptual process, in which the scenes establish the context for one another; c) hypothesis construction by combining descriptions into logical expressions; and d) bi-directional interactions between perceiving new aspects of scenes and constructing hypotheses for the rule that distinguishes categories.