Hello, I'm not sure if this is a bug, or if obstacles are not allowe

Invalid region returned when there are obstacles that exceed the bounds. about iris-distro HOT 2 OPEN

rdeits commented on June 3, 2024

Invalid region returned when there are obstacles that exceed the bounds.

from iris-distro.

Comments (2)

rdeits commented on June 3, 2024

Hey, thanks for the detailed report! (And sorry it took me two months to reply...). This is definitely a bug, and I'll see if I can figure out what's going on.

from iris-distro.

rdeits commented on June 3, 2024

Thanks again for making this so easy to reproduce!

It turns out that, as far as I can tell, this is not exactly an IRIS bug, but instead an issue with cddlib. IRIS is actually doing the right thing, but the points returned by getDrawingVertices() (internally computed by cddlib) are just total garbage. To demonstrate, try looking at the ellipsoids that IRIS produces:

plot_bounds(big_bounds, alpha=0.3, facecolor='none', edgecolor='black')
plt.xlim([minx-1, maxx+1])
plt.ylim([miny-1, maxy+1])

for obs in obstacles:
    vertices = np.array(list(zip(*obs)))
    plot_polygon(vertices,facecolor='blue', alpha=0.5)

# Plot seed
plt.plot(seed[0], seed[1], 'xr')
ax = plt.gca()
ir.getEllipsoid().draw(ax)
plot_bounds(small_bounds, alpha=0.3, facecolor='yellow', edgecolor='black')

The ellipsoid (whose drawing points are not computed by cddlib) is right where I would expect to see it, which means that the polyhedron is probably correct. Internally, IRIS only ever uses the half-space representation of the polyhedron, so its vertices are only computed when you try to draw it.

To verify that something wonky is going on, we can pull out just a subset of the half-spaces from the final polyhedron and try to draw them. Let's use all but the last half-space:

p = ir.getPolyhedron()
plot_polygon(irispy.Polyhedron(p.getA()[:-1],
                               p.getB()[:-1]).getDrawingVertices(), 
             draw_vertices=True,
             facecolor="green",
             alpha=0.2)

That works fine. The last constraint is:

>>> ir.getPolyhedron().getA()[-1], ir.getPolyhedron().getB()[-1]
(array([-0., -1.]), -2.0)

which is just the constraint that y >= 2.0. That's very clearly consistent with the polyhedron shown above. But actually including that half space gives us the garbage vertices that you're seeing:

p = ir.getPolyhedron()
plot_polygon(irispy.Polyhedron(p.getA()[:],
                               p.getB()[:]).getDrawingVertices(), 
             draw_vertices=True,
             facecolor="green",
             alpha=0.2)

To see if this was an issue with the way IRIS uses cddlib, I passed the exact same A and B to https://github.com/JuliaPolyhedra/CDDLib.jl in Julia, and I got exactly the same garbage vertices that you're seeing here:

julia> using Polyhedra, CDDLib

julia> A = [
       7.2719127679597916902309862052788957953453063964843750000000000000000000000000000000000000000000000000e-01 -6.8643488180003897625169884122442454099655151367187500000000000000000000000000000000000000000000000000e-01;
       -9.9227812777442014890993959852494299411773681640625000000000000000000000000000000000000000000000000000e-01 1.2403272608667256782233323519903933629393577575683593750000000000000000000000000000000000000000000000e-01;
       4.1480457874537551265698201961862334741226732148788869380950927734375000000000000000000000000000000000e-08 -9.9999999999999911182158029987476766109466552734375000000000000000000000000000000000000000000000000000e-01;
       1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+00 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+00;
       0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+00 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+00;
       -1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+00 -0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+00;
       -0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+00 -1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+00;
       ];

julia> b = [
           3.7378473714697459939770851633511483669281005859375 ,
           -3.47297834459160004172417757217772305011749267578125,
           -1.9999989615082682803404168225824832916259765625    ,
           8.                                                  ,
           3.87999999999999989341858963598497211933135986328125,
           -3.75                                                ,
           -2.
       ];

julia> h = SimpleHRepresentation(A, b);

julia> p = polyhedron(h, CDDLibrary());

julia> vrep(p)
V-representation
begin
 2 3 real
 1.0 3.750000823973488 2.0
 3.419486915845482e-14 8.557499217096555e-13 6.838973831690964e-14
end

The same exact A and B inputs, when passed to CDD in "exact" (rational) mode give correct vertices:

julia> p = polyhedron(h, CDDLibrary(:exact));


julia> vrep(p)
V-representation
begin
 5 3 rational
 1//1 160402435284077913733595294199767//40251582856530797108415980109824 4368491638549381//1125899906842624
 1//1 67032365826159611//17875293625971088 2//1
 1//1 23016623785096468//3274978363205447 2//1
 1//1 8//1 4683029438162320//1545713938944383
 1//1 8//1 4368491638549381//1125899906842624
end

julia> Float64.(SimpleVRepresentation(vrep(p)).V)
5×2 Array{Float64,2}:
 3.985    3.88
 3.75     2.0
 7.02802  2.0
 8.0      3.02969
 8.0      3.88

So, ultimately, this just boils down to a lesson I've learned many times over: never trust cddlib in floating-point mode.

from iris-distro.

Invalid region returned when there are obstacles that exceed the bounds. about iris-distro HOT 2 OPEN

Comments (2)

Related Issues (20)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent